PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Pricing in High-dimensions

Adel Javanmard, Hamid Nazerzadeh

arXiv:1609.07574v4stat.MLcs.LG

TL;DR

The paper studies how to price many feature-described products when choice-model parameters are unknown and binary sales data arrive over time. It proposes the sparsity-aware RMLP policy and shows regret O(s0 log d · log T), alongside a lower bound of O(s0 (log d + log T)) for any policy.

  • Problem

    The problem is to minimize revenue regret in high-dimensional dynamic pricing when customer-choice parameters are unknown and must be learned from binary sales data.

  • Method

    RMLP estimates the choice-model parameters by maximum likelihood and uses an ℓ1 regularizer to exploit sparsity.

  • Results

    RMLP has regret O(s0 log d · log T), while no policy can achieve regret better than O(s0 (log d + log T)).

  • Takeaways & Limitations

    The regret scales linearly with sparsity and logarithmically with feature dimension and the time horizon.

  • Takeaways & Limitations

    The main RMLP regret guarantee assumes the market-noise distribution is known to the seller.

Abstract

from arXiv · show

We study the pricing problem faced by a firm that sells a large number of products, described via a wide range of features, to customers that arrive over time. Customers independently make purchasing decisions according to a general choice model that includes products features and customers' characteristics, encoded as $d$-dimensional numerical vectors, as well as the price offered. The parameters of the choice model are a priori unknown to the firm, but can be learned as the (binary-valued) sales data accrues over time. The firm's objective is to minimize the regret, i.e., the expected revenue loss against a clairvoyant policy that knows the parameters of the choice model in advance, and always offers the revenue-maximizing price. This setting is motivated in part by the prevalence of online marketplaces that allow for real-time pricing. We assume a structured choice model, parameters of which depend on $s_0$ out of the $d$ product features. We propose a dynamic policy, called Regularized Maximum Likelihood Pricing (RMLP) that leverages the (sparsity) structure of the high-dimensional model and obtains a logarithmic regret in $T$. More specifically, the regret of our algorithm is of $O(s_0 \log d \cdot \log T)$. Furthermore, we show that no policy can obtain regret better than $O(s_0 (\log d + \log T))$.

1 Introduction

The paper studies dynamic pricing for high-dimensional, feature-based products when customer-choice parameters are unknown and must be learned from binary sales feedback. It proposes a sparsity-aware policy with logarithmic regret and positions the setting relative to existing dynamic-pricing and high-dimensional-learning work.

  • Problem setting: The problem involves pricing products with many features while learning unknown customer-choice parameters from sales outcomes over time.The seller must balance learning valuations against exploiting current knowledge to collect revenue.
  • Contributions: RMLP achieves regret O(s0 log d · log T), while no policy can obtain regret better than O(s0 (log d + log T)).Here d is the number of features, s0 is the sparsity of the true parameter, and T is the horizon.
  • Contributions: RMLP combines maximum-likelihood estimation with an ℓ1 regularizer to exploit models whose valuations depend on a small subset of features.The policy is designed for high-dimensional environments and improves when the optimal parameters are sparse.
  • High-dimensional structure: Sparsity enables accurate parameter estimation and useful regret guarantees even when the feature dimension exceeds the time horizon.The paper notes that structure such as sparsity can make estimation attainable when T < d.
  • Related work: The work relates dynamic pricing to parametric, Bayesian, nonparametric, feature-based, and high-dimensional statistical approaches.Unlike offline 1-bit compressed sensing, pricing simultaneously affects revenue and the information collected for learning.

2 Choice model

The model describes pricing with unknown, potentially sparse parameters governing product valuations, where binary sales reveal information over time. Regret is measured against a clairvoyant policy that knows the parameters and posts revenue-maximizing prices.

  • Choice model: Products arrive with observable feature vectors, and the seller posts prices without observing their market values directly.Feature vectors are independently sampled from an unknown distribution with bounded support.
  • Choice model: The linear valuation model combines augmented product features with unknown parameters and independently distributed idiosyncratic noise.The noise has mean zero and distribution F; nonlinear valuation functions are considered later.
  • Choice model: The seller observes binary sale outcomes, creating an exploration–exploitation problem because the true parameter is initially unknown.A sale occurs when the posted price does not exceed the market value.
  • Choice model: Sparsity is measured by s0, the number of nonzero parameter coordinates, which is unknown to the seller.The model also imposes boundedness and log-concavity assumptions on parameters, features, and the noise distribution.
  • Clairvoyant policy and performance metric: The benchmark price is the revenue-maximizing price under known parameters, and regret is expected revenue loss relative to that clairvoyant policy.The optimal price is characterized through the valuation and noise distribution, while regret also averages over feature-vector randomness.
  • Clairvoyant policy and performance metric: The proposed approach exploits sparsity and achieves a regret bound of O(s0 log T(log d + log T)).The stated result is tight up to a logarithmic factor, with a matching lower-bound discussion supplied elsewhere in the paper.

3 A Regularized Maximum Likelihood Pricing (RMLP) Policy

RMLP operates episodically, estimating the unknown model with regularized maximum likelihood from prior-episode observations and pricing throughout each episode using that estimate. Geometrically growing episodes support progressively more accurate estimates while requiring only logarithmically many updates.

  • RMLP policy: RMLP updates a regularized maximum-likelihood estimate at episode boundaries and uses it to set prices during the next episode.The estimator is obtained from observations in the previous episode, and the resulting price is optimal if the estimate is correct.
  • RMLP policy: The policy uses only previous-episode data, separating estimation samples from the market-value noise affecting prices in the current episode.This episodic construction allows each episode’s model estimate to be analyzed separately.
  • RMLP policy: RMLP updates estimates only at the first period of each episode, resulting in log T updates and lower computational cost.The policy is designed for scalability when sales data arrive at high rates.
  • RMLP policy: Using half of the historical data at each update increases total regret by at most a factor of 2.The stated effect follows from the estimation-error rate in the number of samples.
  • RMLP policy: Geometrically increasing episode lengths improve estimation as episodes progress, and the policy does not require the horizon length in advance.The episode lengths are specified as τk = 2k−1.
  • RMLP policy: The regularization parameter constrains the estimator’s ℓ1 norm, while log-concavity makes the regularized likelihood optimization convex.The regularization choice affects estimator error.

4 Regret analysis

The regret analysis shows that RMLP combines episodic regularized likelihood estimation with sparsity to achieve logarithmic regret in the horizon, while exploiting informative pricing and feature structure.

  • Regret upper bound: O(s0 log d · log T) regret follows for RMLP under the stated assumptions.The bound follows from O(s0 log d) regret per geometrically growing episode and O(log T) episodes.
  • Regret upper bound: RMLP updates estimates only between episodes, making episode prices independent of that episode’s market-value noise.This independence lets the episode objective serve as the negative log-likelihood for the collected samples.
  • Regret upper bound: Restricted eigenvalue structure makes the regularized likelihood strictly convex over sparse vectors and yields more accurate estimates as episodes lengthen.The restricted eigenvalue condition addresses high-dimensional estimation, while the estimation error decreases with episode length.
  • Informative pricing: Any fixed price is informative because changing demand parameters changes aggregate demand proportionally to their parameter distance.This contrasts with settings containing an uninformative optimal price that prevents learning at the best action.
  • Comparison with the “common” regret bound: Unknown price sensitivity can create an uninformative optimal price, producing a worst-case lower bound because informative deviations incur regret.The construction fixes an optimal price at p* = 1 where all demand curves intersect, so pricing there reveals no information.
  • Role of Cmin: The learning rate depends on distribution smoothness, feature-space coverage through Cmin, and parameter sparsity s0.These factors appear in the derived learning bound, while RMLP can still achieve a bound when Cmin = 0.

5 Lower bound on regret

The lower-bound analysis shows that even policies with access to fully observed market values incur nontrivial regret when estimating high-dimensional parameters. This lower bound matches the dynamic policy’s regret up to a logarithmic factor.

  • 5 Lower bound on regret: Theorem 5.1 establishes a regret lower bound for every policy in Π, even when market values are fully observed.This oracle setting is more informative than the binary-feedback pricing problem.
  • 5 Lower bound on regret: The lower-bound proof first relates cumulative pricing regret to minimax parameter-estimation error.The reduction defines Ω0 and bounds regret through the estimation difficulty for θ0.
  • 5 Lower bound on regret: Le Cam’s method reduces estimation to distinguishing parameters in a δ-packing of the feasible parameter space.A packing supplies separated candidate parameters, while small estimation error would imply accurate multi-way testing.
  • 5 Lower bound on regret: The construction samples a parameter uniformly from the packing set and generates Gaussian market values, making the lower bound an information-theoretic testing problem.Fano’s inequality controls the testing error using packing size and mutual information.

6 Nonlinear valuation function

The paper extends RMLP from linear valuations to nonlinear valuation functions represented through a feature mapping and a monotone log-concave transformation. Under stated regularity conditions, the modified policy retains logarithmic regret in T.

  • 6 Nonlinear valuation function: The nonlinear model applies a feature mapping φ and a strictly increasing, log-concave function ψ to capture nonlinear feature dependencies.Examples include log-log, semi-log, and logistic models.
  • 6 Nonlinear valuation function: The feature assumptions require either well-conditioned transformed-feature covariance or an almost-everywhere full-rank derivative with well-conditioned original covariance.These conditions support estimation after applying φ.
  • 6 Nonlinear valuation function: The modified RMLP policy estimates parameters by regularized maximum likelihood and sets prices as ψ(gψ(bµk · ˜xt)) during episodic updates.The construction replaces the original features with ˜xt=(φ(xt),1) and transforms prices through ψ.
  • 6 Nonlinear valuation function: Theorem 6.3 gives the nonlinear RMLP policy regret O(s0 log d · log T) under log-concavity, monotonicity, and the model’s regularity assumptions.The proof bounds price deviation by parameter-estimation error and follows the linear analysis.

7 Knowledge of market noise distribution

The paper considers pricing when the market-noise distribution is known, belongs to a known class, or is completely unknown. It introduces RMLP-2 and DIP variants with regret guarantees under progressively weaker distributional knowledge.

  • 7 Knowledge of market noise distribution: The baseline RMLP analysis assumes the market-noise distribution F is known, so its regret isolates uncertainty about model parameters.The paper identifies distribution-independent pricing as an open practical concern when F is unknown.
  • 7.1 Unknown distribution from a known class: RMLP-2 handles unknown mean and variance within a known log-concave distribution class by using linearly growing episodes and random prices for estimation.Only the first, randomly priced period of each episode contributes to the regularized likelihood.
  • 7.1 Unknown distribution from a known class: Theorem 7.1 provides an upper regret bound for RMLP-2 and states a matching lower-bound order for pricing policies in this unknown-parameter distributional setting.The theorem applies to distributions satisfying the paper’s stated assumptions.
  • 7.2 A distribution-independent pricing policy: DIP addresses completely unknown bounded noise by alternating fixed-length random-price exploration with exploitation based on the current parameter estimate.The bounded-noise, high-signal setting assumes valuations lie in a bounded interval.
  • 7.2 A distribution-independent pricing policy: DIP achieves regret O(s0(log d)√T + δT) against a clairvoyant policy that knows parameters and noise realizations.The bound includes both estimation-dependent and bounded-noise terms.

8 Proof of Theorems

The proofs combine regularized-likelihood estimation bounds with episode-wise regret analysis. Exponentially growing episodes convert shrinking estimation error into total regret O(s0 log d · log T).

  • 8 Proof of Theorems: The regularized estimator’s ℓ2 error scales with sparsity and logarithmically with dimension, supporting high-dimensional pricing.The analysis states that more samples improve estimation accuracy while larger sparsity worsens the bound.
  • 8 Proof of Theorems: The proof bounds per-period regret using the difference between the posted and optimal prices, controlled by parameter-estimation error.Revenue curvature and the Lipschitz property of the pricing function convert estimation error into regret.
  • 8 Proof of Theorems: RMLP uses exponentially growing episodes, so only O(log T) episodes occur by horizon T.This episode schedule is the source of the logarithmic dependence on T after episode-wise regret bounds are summed.
  • 8 Proof of Theorems: The episode analysis separates early inaccurate-estimation episodes from later regimes where sharper estimation bounds apply.The first regime uses a direct regret bound when episodes are too short to estimate µ0 accurately.
  • 8 Proof of Theorems: Combining the episode bounds yields total expected regret O(s0 log d log T).The cumulative episode contribution is O(s0 log d), and the number of episodes is logarithmic in T.

9 Conclusion

The paper develops a computationally efficient dynamic pricing policy for high-dimensional product features, exploiting sparsity to control regret. It also identifies unresolved gaps concerning tight bounds, approximate sparsity, and richer choice models.

  • 9 Conclusion: RMLP exploits demand-parameter structure to obtain regret scaling linearly with sparsity and logarithmically with feature dimension and time horizon.The stated dependence is linear in sparsity, logarithmic in dimension, and O(log^2 T) in the horizon.
  • 9 Conclusion: The paper identifies closing the gap between its upper and lower regret bounds as a natural next step.
  • 9 Conclusion: A further open question is how regret changes when the parameter is only approximately sparse, with approximation error measured by δ.
  • 9 Conclusion: The model assumes one product arrives per period, leaving multiple-product consideration-set choice models for future work.The proposed generalization lets customers choose among products remaining after personal screening.
  • 9 Conclusion: The techniques may also apply to personalized pricing, online-ad reserve prices, assortment optimization, and consumer-choice learning.

A Proof of Proposition 8.1

The proof analyzes the regularized likelihood estimator through gradient concentration, curvature, and restricted-eigenvalue control. These ingredients yield an oracle-style estimation argument under the stated sparsity structure.

  • A Proof of Proposition 8.1: The proof begins from the restricted eigenvalue condition, a standard condition in high-dimensional statistical estimation.
  • A Proof of Proposition 8.1: The proof transfers restricted-eigenvalue control from the population covariance to the empirical covariance using matrix closeness.
  • A Proof of Proposition 8.1: Gradient concentration is established using bounded martingale differences, Azuma-Hoeffding, and a union bound over d feature coordinates.The resulting event has probability at least 1 − 1/d.
  • A Proof of Proposition 8.1: The likelihood Hessian is lower-bounded by ℓ_W times the empirical feature covariance after controlling the relevant parameter range.
  • A Proof of Proposition 8.1: Optimality of the ℓ1-regularized estimator produces a basic inequality relating prediction error, penalty terms, gradient size, and parameter error.
  • A Proof of Proposition 8.1: Applying triangle, Cauchy-Schwarz, and restricted-eigenvalue arguments converts the basic inequality into an oracle-style error bound.

A.1 Proof of Proposition A.2

This appendix establishes the empirical restricted-eigenvalue property needed for the estimator analysis. It derives the result from subgaussian covariance concentration and stability of the restricted-eigenvalue condition under matrix perturbations.

  • A.1 Proof of Proposition A.2: The proof uses a perturbation lemma: restricted-eigenvalue control for one matrix transfers to a sufficiently close matrix in maximum norm.
  • A.1 Proof of Proposition A.2: Subgaussian design concentration supplies the required closeness between empirical and population covariance matrices when n is sufficiently large relative to s_0 log d.The stated sample-size condition is n ≥ c_0 L s_0 log d.
  • A.1 Proof of Proposition A.2: Assumption 2.2 gives the population covariance a restricted-eigenvalue constant at least C_min, which supports the empirical covariance argument.
  • A.1 Proof of Proposition A.2: The argument specializes the subgaussian result using bounded feature coordinates, since bounded random variables are subgaussian.

B Proof of Proposition 8.3

The proof bounds estimation-error terms by combining covariance concentration, gradient concentration, regularized-likelihood inequalities, and properties of the valuation model. It then assembles the separate bounds into the desired result.

  • B Proof of Proposition 8.3: A covariance concentration event is shown to hold with probability at least 1 − e^(-c n^2) when n exceeds a constant multiple of d.
  • B Proof of Proposition 8.3: Gradient concentration defines an event controlling the infinity norm of the likelihood gradient through an Azuma-Hoeffding argument.
  • B Proof of Proposition 8.3: The proof decomposes the target bound into three terms and treats each term separately.
  • B Proof of Proposition 8.3: Lemma B.1 bounds the estimation error on the intersection of covariance and gradient-control events when γ exceeds λ/2.
  • B Proof of Proposition 8.3: The regularized-likelihood inequality follows from estimator optimality and the log-concavity of the loss function.
  • B Proof of Proposition 8.3: For the Gaussian valuation specialization, monotonicity of the virtual valuation and Gaussian tail bounds are used to establish properties of the relevant functions.

C.4 Proof of Lemma 8.8

The proof derives two lower bounds for a truncated second moment by splitting according to whether δ is below or above ||v||2 and using tail bounds for the normalized variable.

  • C.4 Proof of Lemma 8.8: The proof rewrites the expectation using the tail probability of the normalized variable Ẑ.This representation supports the subsequent case-specific lower bounds.
  • C.4 Proof of Lemma 8.8: The proof splits the lower-bound analysis into the cases δ ≤ ||v||2 and δ ≥ ||v||2.These cases are used to bound the right-hand side of the preceding inequality separately.
  • C.4 Proof of Lemma 8.8: Var(Ẑ) = 1 provides the variance property used to derive an additional bound.The proof combines this property with tail-probability estimates and a Chernoff bound.
  • C.4 Proof of Lemma 8.8: The two cases and tail estimates are summarized as a lower bound on E(min(Z2, δ2)).The supplied conclusion states a constant-factor lower bound involving min(||v||2, δ2).

C.5 Proof of Lemma 8.9

The proof establishes lower bounds through packing and hypothesis testing, verifies a covariance nondegeneracy condition, and derives pricing and gradient properties used in the analysis.

  • C.5 Proof of Lemma 8.9: Fano’s inequality applied to a δ-packing yields a lower bound on the hypothesis-testing error and ultimately the minimax risk.The construction uses sparse vectors separated in Hamming distance, with packing size controlled by the ambient dimension and sparsity.
  • C.5 Proof of Lemma 8.9: The lower-bound argument also considers an oracle that reveals the true support, where least squares attains the optimal minimax ℓ2 rate.This separates support uncertainty from estimation on the known support.
  • C.5 Proof of Lemma 8.9: A 0-property for φ together with positive definiteness of Σφ implies the required nondegeneracy condition.The contradiction argument rules out a nonzero vector v with vTΣφv = 0.
  • C.5 Proof of Lemma 8.9: Under the pricing model, a purchase occurs when the transformed valuation exceeds β0p, and the optimal price solves the resulting first-order condition.The supplied passages state that the expected revenue is formed from this purchase condition and that p∗t is obtained from the corresponding equation.
  • C.5 Proof of Lemma 8.9: Uniform exploration prices make the quadratic-loss gradient unbiased at the true parameter, enabling concentration via Azuma–Hoeffding and a union bound.The proof states E(ξt(µ0)) = 0 and then controls the feature-coordinate deviations.
  • C.5 Proof of Lemma 8.9: A union bound over indices gives ||E(k)||∞ ≤ 3(log d)/τk with probability at least 1 − 8/d2.This bound is used together with the preceding relation to complete the claim.
Loading 1609.07574v4…