High-Dimensional Dynamic Pricing under Non-Stationarity: Learning and Earning with Change-Point Detection

Zifeng Zhao, Feiyu Jiang, Yi Yu, Xi ChenSSRN 2023 · DOI

TL;DR

This paper tackles the challenge of dynamic pricing in online marketplaces where consumer behavior can change unexpectedly over time. They introduce a novel algorithm, CPDP, that effectively detects these changes and adapts pricing strategies to maximize revenue, achieving near-optimal performance even when the magnitude of these changes is unknown.

What Problem Does This Paper Address?

In today's digital economy, businesses can dynamically adjust prices to maximize profits. This often involves learning about consumer preferences based on available data (like demographics or past purchase history) and then exploiting this knowledge to set optimal prices. However, a significant real-world complication is "non-stationarity" – consumer behavior isn't static. External events (like economic downturns or pandemics) or shifts in trends can cause demand patterns to change abruptly and unpredictably. Traditional dynamic pricing models often assume a stable demand function, which can lead to suboptimal revenue when these changes occur. This paper addresses the problem of dynamic pricing in a high-dimensional setting (where many factors influence demand) under non-stationarity, specifically when the timing and magnitude of these demand shifts are unknown. The goal is to develop a pricing strategy that can learn the demand model, detect changes, and adapt quickly to maintain revenue maximization.

Methods

The core of this paper is the Change-Point Detection Assisted Dynamic Pricing (CPDP) algorithm. It combines three key components:

  1. High-Dimensional GLM Estimation: The demand model is assumed to follow a generalized linear model (GLM) with many features (high-dimensional). The authors use the Lasso estimator to learn the model parameters efficiently, which is standard for high-dimensional settings.
  2. Change-Point Detection: This is the novel part. They propose a penalized likelihood-based online change-point detection algorithm specifically designed for high-dimensional GLMs. This algorithm is designed to detect changes with minimal delay and control false alarms, achieving optimal localization error rates.
  3. Exploration-Exploitation Strategy: Like many dynamic pricing algorithms, CPDP balances exploring different prices to learn more about demand (exploration) with setting prices that are believed to be optimal based on current knowledge (exploitation). A key innovation here is an "accelerated exploration mechanism" that increases the frequency of price experiments after detecting a change-point. This is crucial because data collected before a change-point becomes less relevant afterward.

The algorithm operates in cycles. Each cycle involves a period of price experimentation (exploration), followed by change-point detection. If a change is detected, the system restarts. If not, the algorithm proceeds to a period of price exploitation based on the learned model.

Datasets

The paper uses a real-world dataset from an online auto loan lender for their case study. This dataset includes information about loan applications, consumer characteristics (like FICO score), and economic factors. They also conduct extensive simulations on synthetic data to evaluate their algorithm under various controlled scenarios.

Key Insights and Ideas

  • Non-stationarity is a major revenue drain: Ignoring changes in consumer behavior can lead to significant revenue losses. The CPDP algorithm's ability to detect and adapt to these changes is crucial for maximizing profits.
  • Accelerated exploration is key for non-stationarity: Simply continuing to explore at a fixed rate after a change-point is inefficient. By increasing exploration after detecting a change, CPDP ensures that the learning process quickly adapts to the new demand patterns.
  • Optimal change-point detection is possible for GLMs: Developing change-point detection for complex models like high-dimensional GLMs is challenging. The paper presents a novel algorithm that achieves theoretical optimality in detecting these changes.
  • Regret scales optimally with change-points: The theoretical analysis shows that CPDP's regret (revenue loss) scales favorably with the number of change-points, thanks to the accelerated exploration mechanism. This is a significant improvement over previous methods that might scale linearly.

Key Results

  • The proposed CPDP algorithm achieves a near-optimal regret of order $O(s\sqrt{Y_T T \log(Td)})$, where $s$ is the sparsity level, $Y_T$ is the number of change-points, $T$ is the total number of consumers, and $d$ is the dimension of the feature space.
  • The paper provides a minimax lower bound on the regret of $\Omega(\sqrt{T Y_T})$, demonstrating the near-optimality of CPDP.
  • The novel online change-point detection algorithm for high-dimensional GLMs achieves optimal minimax localization error rates.
  • Numerical experiments on both synthetic and real-world auto loan data show that CPDP significantly outperforms baseline methods, especially in non-stationary environments. For instance, in the auto loan case study, CPDP reduced revenue loss by $1.3 \sim 2.3$ million dollars compared to a naive approach.

Limitations and Future Work

  • Privacy: The current model assumes full access to consumer-level transaction data. The authors acknowledge that with increasing privacy concerns, developing dynamic pricing policies that handle non-stationarity while respecting privacy constraints is an important area for future research.
  • Lower bound conjecture: While the paper provides a lower bound of $\Omega(\sqrt{TY_T})$, the authors conjecture that a sharper lower bound of $\Omega(s\sqrt{TY_T})$ might be possible, similar to stationary settings.
  • Smooth changes: The current framework focuses on abrupt change-points. Extending the methods to handle smooth or gradual changes in demand could be a valuable direction.

Summary updated

BibTeX
@misc{zhao2023high,
  author = {Zifeng Zhao and Feiyu Jiang and Yi Yu and Xi Chen},
  title = {{High-Dimensional Dynamic Pricing under Non-Stationarity: Learning and Earning with Change-Point Detection}},
  year = {2023},
  doi = {10.2139/ssrn.4387917},
  howpublished = {SSRN},
}
Figure