On Non-Stationary Dynamic Pricing: Adaptivity and Optimality

• URL: http://arxiv.org/abs/2607.24115v1
• Date: Mon, 27 Jul 2026 07:56:56 GMT
• Title: On Non-Stationary Dynamic Pricing: Adaptivity and Optimality
• Abstract summary: We study the contextual dynamic pricing problem under non-stationarity.<n>A firm sells products to $T$ sequentially arriving consumers that behave according to an unknown demand model that can change over time.<n>To achieve optimal revenue (i.e., least regret), the firm needs to learn and exploit the unknown GLMs while monitoring for potential changes.
• Score: 2.3037277758579364
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the contextual dynamic pricing problem under non-stationarity, where a firm sells products to $T$ sequentially arriving consumers that behave according to an unknown demand model that can change over time. The demand model is assumed to be a generalized linear model (GLM), allowing for a feature vector in $\mathbb{R}^d$ that encodes products and consumer information. To achieve optimal revenue (i.e., least regret), the firm needs to learn and exploit the unknown GLMs while monitoring for potential changes. We propose a multiscale change-point detection based algorithm that achieves a regret of order $\widetilde{O}(\sqrt{s_TdT}\wedge\{V_T^{1/3}d^{1/3}T^{2/3}+\sqrt{dT}\})$, where $s_T$ is the number of piecewise stationary segments and $V_T$ is a newly defined notion of design-adjusted variation budget of model parameters. Our algorithm is adaptive and does not require knowing $s_T$ or $V_T$. Moreover, to our knowledge, this is the first dynamic pricing algorithm that is adaptive to the nature of changes and achieves the best-of-both-worlds rate, thus closing a long-standing gap in the literature. We remark that, due to the varying contexts, existing works in the adaptive non-stationary bandit literature cannot be applied to achieve optimality for contextual dynamic pricing. The regret is further accompanied with a newly constructed minimax lower bound, confirming the optimality of our algorithm (up to logarithmic factors). Extensive numerical experiments are conducted to illustrate the efficiency and robustness of the proposed algorithm in non-stationary dynamic pricing.

Related papers

• Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity [68.54852541944625]
  Black-box optimization is applied when gradients are unavailable and objective evaluations rely on expensive simulations.<n>We show how the choice of oracle type, noise model, and optimization scheme induces explicit wall-clock-optimal choices for the algorithmic parameters.
  arXiv  Detail & Related papers  (2026-05-29T14:24:54Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
  This paper revisits the weighted strategy for non-stationary parametric bandits.<n>We propose a simpler weight-based algorithm that is as efficient as window/restart-based algorithms.<n>Our framework can be used to improve regret bounds of other parametric bandits.
  arXiv  Detail & Related papers  (2026-01-03T04:50:21Z)
• Optimal Robust Recourse with $L^p$-Bounded Model Change [1.1151457846264181]
  Models often get updated to reflect changes in the data distribution or environment.<n>We provide a new algorithm that provably computes the optimal robust recourse for generalized linear models.
  arXiv  Detail & Related papers  (2025-09-25T15:11:51Z)
• Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs [63.47351876442425]
  We study episodic linear mixture MDPs with the unknown transition and adversarial rewards under full-information feedback. We propose a novel algorithm that combines the benefits of two popular methods: occupancy-measure-based and policy-based. Our algorithm enjoys an $widetildemathcalO(d sqrtH3 K + sqrtHK(H + barP_K$)$ dynamic regret, where $d$ is the feature dimension.
  arXiv  Detail & Related papers  (2024-11-05T13:55:52Z)
• Contextual Dynamic Pricing: Algorithms, Optimality, and Local Differential Privacy Constraints [10.057344315478709]
  We study contextual dynamic pricing problems where a firm sells products to $T$ sequentially-arriving consumers.<n>We first show the optimal regret is of order $sqrtdT$, up to logarithmic factors.<n>We extend our study to dynamic pricing under mixed privacy constraints, improving the privacy-utility tradeoff by leveraging public data.
  arXiv  Detail & Related papers  (2024-06-04T15:44:10Z)
• Smoothness-Adaptive Dynamic Pricing with Nonparametric Demand Learning [0.0]
  We study the dynamic pricing problem where the demand function is nonparametric and H"older smooth. We focus on adaptivity to the unknown H"older smoothness parameter $beta$ of the demand function.
  arXiv  Detail & Related papers  (2023-10-11T15:02:13Z)
• Structured Dynamic Pricing: Optimal Regret in a Global Shrinkage Model [50.06663781566795]
  We consider a dynamic model with the consumers' preferences as well as price sensitivity varying over time. We measure the performance of a dynamic pricing policy via regret, which is the expected revenue loss compared to a clairvoyant that knows the sequence of model parameters in advance. Our regret analysis results not only demonstrate optimality of the proposed policy but also show that for policy planning it is essential to incorporate available structural information.
  arXiv  Detail & Related papers  (2023-03-28T00:23:23Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits [20.128001589147512]
  We study the problem of non-stationary dueling bandits and provide the first adaptive dynamic regret algorithm for this problem. We show a near-optimal $tildeO(sqrtStexttCW T)$ dynamic regret bound, where $StexttCW$ is the number of times the Condorcet winner changes in $T$ rounds.
  arXiv  Detail & Related papers  (2022-10-25T20:26:02Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  We introduce a new family of oracle-efficient algorithms for $varepsilon$-misspecified contextual bandits. We obtain the first algorithm that achieves the optimal $O(dsqrtT + varepsilonsqrtdT)$ regret bound for unknown misspecification level.
  arXiv  Detail & Related papers  (2021-07-12T21:30:41Z)
• Dynamic Pricing and Learning under the Bass Model [16.823029377470366]
  We develop an algorithm that satisfies a high probability regret guarantee of order $tilde O(m2/3)$; where the market size $m$ is known a priori. Unlike most regret analysis results, in the present problem the market size $m$ is the fundamental driver of the complexity.
  arXiv  Detail & Related papers  (2021-03-09T03:27:33Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.