Technical Summary: Non-Stationary Dynamic Pricing with Adaptivity and Optimality

1. Problem Formulation

The paper addresses the contextual dynamic pricing problem under non-stationarity. A firm sells products to $T$ sequentially arriving consumers. At each time $t$, a context vector $z_t \in \mathbb{R}^d$ (encoding product and consumer information) is observed. The firm sets a price $p_t \in [l, u]$ and observes a demand response $y_t$.

The demand model is assumed to be a Generalized Linear Model (GLM) with an unknown parameter $\theta_t \in \mathbb{R}^{2d}$ that evolves over time. Specifically, the expected demand is given by:
$$\mathbb{E}[y_t | x_t, \theta_t] = \psi'(x_t^\top \theta_t) = \psi'(z_t^\top \alpha_t - (z_t^\top \beta_t)p_t)$$
where $x_t = (z_t^\top, -p_t z_t^\top)^\top$.

The core challenge is that the parameter sequence $\{\theta_t\}_{t=1}^T$ is non-stationary and its nature is unknown to the firm. The paper considers two distinct regimes of non-stationarity:

1. Structured Non-Stationarity: The parameters are piecewise constant with $s_T - 1$ unknown abrupt change-points.
2. Unstructured Non-Stationarity: The parameters vary smoothly or arbitrarily, subject to a total variation budget $V_T$.

The objective is to design a pricing policy that minimizes regret, defined as the cumulative revenue loss compared to a clairvoyant who knows the true sequence $\{\theta_t\}$ and the optimal price $p_t^*$ at every step. Crucially, the algorithm must be adaptive, meaning it should achieve optimal performance without prior knowledge of whether the environment is structured or unstructured, nor knowledge of the specific values of $s_T$ or $V_T$.

2. Methodology: MCP-DP Algorithm

The authors propose the Multiscale Change-Point Detection based Dynamic Pricing (MCP-DP) algorithm. The algorithm operates in epochs, which are further partitioned into dyadic blocks. Within each block, it combines an Explore-Then-Commit (ETC) strategy with a novel Multiscale Sampling Scheme (MSS) and a Likelihood-Ratio Test (LRT).

Key Components:

• Reference Model Estimation: At the start of a block, the algorithm estimates a reference parameter $\hat{\theta}$ using Maximum Likelihood Estimation (MLE) from a price exploration set accumulated in the previous block.
• Localized Price Exploration: Instead of uniform price sampling, MCP-DP uses a localized perturbation scheme around the greedy price $p^*(z_t, \hat{\theta})$. This reduces regret during exploration while maintaining statistical validity (ensuring the design matrix remains well-conditioned).
• Multiscale Scheduling (MSS): To detect changes of unknown magnitude and timing, MSS randomly schedules price exploration intervals of varying lengths (scales) within each block. Shorter intervals are sampled more frequently to detect large, abrupt changes, while longer intervals detect small, gradual drifts.
• Likelihood-Ratio Test (LRT): At the end of each scheduled exploration interval, the algorithm performs an LRT comparing the reference model $\hat{\theta}_{pre}$ against a new MLE $\hat{\theta}_J$ fitted on that interval.
  • The test statistic is $\Lambda_J(\hat{\theta}_{pre}) = L_J(\hat{\theta}_{pre}) - L_J(\hat{\theta}_J)$.
  • If the statistic exceeds a threshold $\gamma \propto d \log(dT)$, the algorithm assumes a significant change has occurred, terminates the current epoch, and restarts with a new epoch.
• Adaptivity: The multiscale nature of the exploration allows the algorithm to simultaneously handle both abrupt changes (structured) and smooth variations (unstructured) without needing to know the specific regime or parameters ($s_T, V_T$) in advance.

3. Key Contributions

1. The MCP-DP Algorithm and Regret Bounds

The paper introduces MCP-DP, the first dynamic pricing algorithm proven to be adaptive to both structured and unstructured non-stationarity.

• Regret Upper Bound: The algorithm achieves a regret of order:
  $$\tilde{O}\left( \sqrt{s_T d T} \wedge \left( \sqrt{dT} + d^{1/3} V_T^{1/3} T^{2/3} \right) \right)$$
  This bound represents the "best-of-both-worlds" rate, matching the optimal rates for purely structured and purely unstructured settings simultaneously.
• No Prior Knowledge: The algorithm does not require knowledge of the number of change-points $s_T$, the variation budget $V_T$, the minimal change size, or the segment lengths.

2. Design-Adjusted Variation Budget

The authors introduce a new concept called the design-adjusted variation budget ($V_T$). Unlike existing variation budgets that measure the raw distance between parameters $\|\theta_t - \theta_{t-1}\|$, $V_T$ weights the variation by the context distribution (specifically the design matrix $\Sigma_z$).

• Significance: This provides a sharper characterization of non-stationarity in contextual settings. It captures the intuition that changes in parameters along directions rarely represented by the context $z_t$ have less impact on demand and regret. This definition generalizes and tightens existing bounds in the literature.

3. Minimax Lower Bounds

The paper establishes a new minimax lower bound for non-stationary contextual dynamic pricing:
$$\Omega\left( \sqrt{s_T d T} \wedge \left( \sqrt{dT} + d^{1/3} V_T^{1/3} T^{2/3} \right) \right)$$

• Dimensionality Dependence: This is the first lower bound in dynamic pricing literature to explicitly characterize the dependence on the context dimension $d$ for both structured and unstructured cases.
• Technical Novelty: The proof utilizes a new construction based on Assouad's lemma to handle the diverging dimension $d$ as $T \to \infty$, connecting the regret to a multiple-classification error problem.

4. Theoretical and Statistical Foundations

• High-Probability MLE Bounds: The authors derive a new high-probability upper bound on the prediction error of MLE for a mixture of GLMs under non-stationarity. This result is of independent interest and underpins the optimality of the LRT.
• LRT as a Regret Surrogate: The paper proves that the LRT statistic serves as a surrogate for the unobserved exploitation regret, allowing the algorithm to detect excessive regret without knowing the true parameters.

4. Results and Empirical Validation

Extensive numerical experiments were conducted on both linear and logistic demand models with varying context dimensions ($d$) and time horizons ($T$).

• Baseline Settings: MCP-DP was compared against CPDP (optimized for abrupt changes) and MWDP (optimized for smooth changes).
  • In stationary settings, MCP-DP matched the performance of CPDP and outperformed MWDP.
  • In abrupt change settings, MCP-DP matched CPDP.
  • In smooth change settings, MCP-DP matched MWDP.
  • Crucially, MCP-DP maintained robust performance across all regimes without tuning, whereas the benchmarks failed when the environment did not match their specific assumptions.
• Complex Settings: In scenarios with adversarial change patterns (where CPDP's fixed schedule fails) or diverging change counts/budgets, MCP-DP demonstrated superior robustness and lower regret compared to the non-adaptive benchmarks.
• Design-Adjusted Budget Validation: Experiments with different context distributions (Z1 vs. Z2) confirmed that the performance of MCP-DP remains stable when measured against the design-adjusted budget, whereas standard $L_2$ variation budgets failed to explain the stability.

5. Significance and Claims

The paper claims to close a long-standing gap in the dynamic pricing literature. Prior works on non-stationary pricing were non-adaptive, requiring separate algorithms for abrupt vs. smooth changes and often demanding knowledge of change magnitudes or budgets.

• First Adaptive Algorithm: MCP-DP is presented as the first algorithm to achieve optimal regret rates for both structured and unstructured non-stationarity in a single, adaptive framework without requiring prior knowledge of the change nature ($s_T$ or $V_T$).
• Optimality: The algorithm is shown to be minimax optimal (up to logarithmic factors), matching the newly derived lower bounds.
• Methodological Advance: The work highlights that existing adaptive bandit literature (e.g., switching bandits) cannot be directly applied to contextual dynamic pricing due to the continuous action space and the fact that the "best arm" (optimal price) changes with the context. The proposed LRT-based approach specifically addresses this by tracking the regret of the pricing policy relative to the context distribution.

The authors note that while the current work assumes stochastic contexts, extending the method to adversarial contexts remains a future direction, as the current LRT success relies on the stochastic nature of the design matrix.