Contextual Dynamic Pricing with Heterogeneous Buyers

AI summary

Overview

Research area: Online learning theory, specifically contextual dynamic pricing and contextual search, with connections to Lipschitz bandits and adaptive discretization.

Technical level: Advanced. The paper is a theoretical machine-learning paper built on regret analysis, lower-bound constructions, and complexity measures such as the disagreement coefficient and zooming dimension. There are no experiments, datasets, or empirical benchmarks in the content.

Scope: The paper introduces and analyzes contextual dynamic pricing when the buyer population is heterogeneous, meaning each arriving buyer's valuation type is drawn from an unknown distribution supported on K* distinct types, rather than assuming a single shared type as in prior work.

What This Paper Is About

In standard contextual dynamic pricing, a seller repeatedly posts prices for products described by a d-dimensional feature vector (context), and a buyer either purchases or does not based on whether their valuation exceeds the posted price. Prior algorithms for this problem assume all buyers share one fixed, unknown valuation type. This paper instead assumes the buyer's type is drawn from a fixed but unknown distribution D* whose support has size K*, so buyers genuinely differ from one another. The goal is to design seller algorithms whose revenue loss (regret) relative to a seller who knows D* grows as slowly as possible in the time horizon T, the context dimension d, and the degree of heterogeneity K*.

Key Contributions

1. A new problem formulation: The paper initiates the study of contextual dynamic pricing with a heterogeneous buyer population, where the type θ_t in round t is sampled independently from an unknown distribution D* over types Θ ⊆ [0,1]^d, and the degree of heterogeneity is measured by K* = |supp(D*)|, assumed to satisfy K* > 1. The homogeneous setting is recovered when D* is supported on a single type.

2. A contextual algorithm with optimal d and T dependence: The authors adapt optimistic posterior sampling (OPS, from Zhang 2022) to heterogeneous contextual pricing, handling an infinite model class and unknown K*, and prove a regret bound of Õ(K*√(dT)). They complement this with a lower bound of Ω(√(K* d T)) for sufficiently large T = Ω(dK*³), showing the bound is tight in d and T up to logarithmic terms.

3. A refined non-contextual algorithm: For the non-contextual case (d = 1), they propose ZoomV, a variance-aware zooming algorithm that combines zooming (adaptive discretization) from Lipschitz bandits with variance-aware confidence intervals, achieving Õ(√(KT)) and thereby resolving the optimal dependence on K in that setting.

4. Results under stronger type observability: They analyze two models where the learner can identify the arriving type, namely a discrete identifier z_t ∈ [K*] (where a computationally efficient algorithm matches the Õ(K*√(dT)) bound) and the full type vector θ_t ∈ B^d (where regret improves to Õ(√(min{K*,d}T))).

Main Findings

• Main contextual upper bound: OPS over a finite covering of the class of all distributions over K* types, with log cardinality dK* log T, attains regret Õ(K*√(dT)); this holds even when K* is unknown, handled by initializing OPS with a non-uniform prior over models.

• Lower bound: For T = Ω(dK³), no algorithm can do better than Ω(√(K d T)), establishing optimality of the upper bound with respect to both d and T up to logarithmic terms.

• Disagreement coefficient bound: For any fixed context, the demand function induced by D* has at most K* jumps, creating K*+1 intervals. Using a lemmas showing that the disagreement coefficient of non-increasing functions is at most 2 and that an N-composite class has disagreement coefficient at most N times that of the base class, the paper proves c ≤ 2(K*+1) = O(K*). Notably, despite an infinite action space (a continuum of prices), the disagreement coefficient matches what would arise with K* actions.

• Warm-up finite-class result: Under a realizability assumption that D* lies in a known finite class D, OPS with optimism strength λ = √(log(|D|)/KT) achieves regret Õ(√(K* T log|D|)).

• Non-contextual bound: ZoomV achieves Õ(min{√(KT), T^{2/3}}), improving on the O(T^{2/3}) that the standard zooming analysis gives, and also delivering T^{2/3} regret when K ≫ T^{1/3} without changing the algorithm.

• Variance-aware complexity measure: ZoomV's regret scales with a novel variance-aware zooming dimension ZoomDimV rather than the standard zooming dimension ZoomDim. While ZoomDim can equal 1 for worst-case instances, the paper shows ZoomDimV is 0, with a lower-order scaling constant of at most K*.

• Contrast with prior non-contextual work: Cesa-Bianchi et al. (2019) established matching upper and lower bounds for non-contextual pricing of heterogeneous buyers only when all types are "well-separated." Independent and concurrent work by Bacchiocchi et al. (2025) removes that assumption and also achieves Õ(√(K*T)), but both use binary search techniques specialized to the piecewise-linear revenue function; ZoomV is instead a generic one-sided Lipschitz bandits algorithm that uses the revenue structure only in its analysis.

• Effect of observing types: A discrete identifier z_t ∈ [K*] lets a computationally efficient algorithm match the Õ(K*√(dT)) bound, while observing the full type vector θ_t ∈ B^d reduces regret to Õ(√(min{K*,d}T)), showing that richer feedback lowers complexity.

• Structural lemma used throughout: The expected revenue function satisfies one-sided Lipschitzness: for 0 ≤ p < p' ≤ 1, rev_Q(p') − rev_Q(p) ≤ dem_Q(p)(p' − p) ≤ p' − p. This is what allows Lipschitz bandit techniques to be applied despite the discontinuous revenue curve.

Methodology in Plain English

The paper is theoretical: it defines a model of repeated seller–buyer interaction, designs algorithms, and proves bounds on regret relative to a seller who knows the true buyer-type distribution.

The core technical idea is to treat each candidate buyer-type distribution as a "model" in a large family and to maintain a posterior over models. In each round the algorithm samples a model from that posterior and best-responds to it. The posterior is updated using a squared-error penalty for models that predict demand poorly (model mismatch) minus an optimism bonus that favors models offering high potential revenue. This is the optimistic posterior sampling (OPS) recipe of Zhang (2022), adapted here to a setting with a continuum of prices and with stochasticity that is context-dependent and non-i.i.d.

Three obstacles had to be overcome. First, buyer types are not observed, so classical binary-search or knowledge-set methods cannot be run separately per type. Second, the optimal policy depends on context, not on a fixed type. Third, a continuum of actions means naïve discretization (for example, EXP4-style algorithms) scales poorly.

To handle these, the authors bound the disagreement coefficient, a measure of per-context structural complexity, by exploiting the fact that demand under K* types is piecewise constant with K*+1 intervals, and by proving a decomposition lemma for composite function classes. To move from a finite model class to the infinite family of distributions, they perturb recommended prices conservatively — which is safe because revenue is one-sided Lipschitz — and construct a coupling between the real trajectory and one where D* lies in a finite cover. Unknown K* is handled with a non-uniform prior.

For the non-contextual case, they replace binary search with a general zooming algorithm equipped with variance-aware confidence intervals; the pricing structure enters only in the analysis, where it is used to bound a variance-aware zooming dimension.

Why This Matters

Impact on research. The paper breaks the homogeneity assumption that underpins most prior contextual pricing and contextual search work. It shows that heterogeneity, modeled as an unknown distribution over K* types, is learnable at a cost that scales with K* rather than with an infinite or discretized action count, and it establishes matching lower bounds in d and T. It also connects pricing to the broader Lipschitz bandits and variance-aware bandit literature, and it complements concurrent work (Bacchiocchi et al., 2025) that attacks the same non-contextual problem with different, structure-specialized techniques. The results on observing type identifiers or type vectors quantify how much richer feedback helps.

Real-world applications (settings that match the model rather than experiments reported in the paper):

• E-commerce and retail pricing, where sellers post prices for many items described by features (context) and face a customer population with genuinely different willingness to pay.
• Travel and hospitality pricing, where the same flight or room is offered to customer segments with distinct valuation profiles.
• Ride-hailing and delivery surge pricing, where demand and willingness to pay vary by rider segment and by location/time context.
• Subscription or digital-goods pricing, where users differ in how much they value features and the seller sees only purchase/no-purchase feedback each period.

Industry relevance. Firms that repeatedly set prices and observe only binary purchase outcomes operate under exactly the feedback constraints studied here. The paper's central messages for practice are that heterogeneity should be modeled explicitly rather than averaged away, that the cost of doing so scales with the number of distinct buyer types, and that identifying even a coarse segment label can materially reduce that cost.

Future Directions

• Tightening the K dependence in the contextual case.* The contextual upper bound is Õ(K*√(dT)) while the lower bound is Ω(√(K* d T)); the paper resolves the optimal K* dependence only in the non-contextual case, so whether the contextual bound can be improved in K* remains open.

• Computational efficiency. The paper describes its contextual algorithms as statistically efficient but computationally inefficient; designing computationally efficient variants with the same guarantees is an open direction.

• Log-loss OPS and logarithmic regret for K = 1.* The authors raise the question of whether OPS with log loss achieves regret scaling logarithmically in T when K* = 1, noting that log loss eliminates models predicting impossible feedback, mirroring elimination-based methods.

• Extending to other feedback structures and richer observability. Section 5 shows that observing a discrete type identifier or the full type vector improves regret; further work could characterize the full spectrum between no type observability and full observability, and the paper also notes that corruptions and approximate homogeneity (Krishnamurthy et al., 2023; Paes Leme et al., 2022) remain only partial steps toward full heterogeneity.

Target Audience

This paper is for researchers in online learning, bandit theory, and algorithmic pricing who are comfortable with regret analysis, lower-bound constructions, and complexity measures such as the disagreement coefficient and zooming dimension. It is most directly useful to theorists extending contextual search or contextual pricing beyond homogeneous buyers, and to applied researchers in revenue management and marketplaces who want to understand what guarantees are possible when buyer populations are genuinely heterogeneous and only binary purchase feedback is observed. Readers seeking empirical benchmarks or implementations will not find them here, since the content is purely theoretical.

Authors’ abstract

We initiate the study of contextual dynamic pricing with a heterogeneous population of buyers, where a seller repeatedly posts prices (over $T$ rounds) that depend on the observable $d$-dimensional context and receives binary purchase feedback. Unlike prior work assuming homogeneous buyer types, in our setting the buyer's valuation type is drawn from an unknown distribution with finite support size $K_{\star}$. We develop a contextual pricing algorithm based on optimistic posterior sampling with regret $\widetilde{O}(K_{\star}\sqrt{dT})$, which we prove to be tight in $d$ and $T$ up to logarithmic terms. Finally, we refine our analysis for the non-contextual pricing case, proposing a variance-aware zooming algorithm that achieves the optimal dependence on $K_{\star}$.