Optimal Contextual Pricing in Non-stationary Environments

We study contextual dynamic pricing in a non-stationary environment. In each round, a seller observes a buyer's context, posts a price, and receives only binary purchase feedback. The buyer's value is linear in the context and an unobserved feature vector that may change over time, subject to a known total variation budget $V$. We measure dynamic regret against the first-best benchmark that extracts each buyer's full value. For identical contexts, we develop a deterministic algorithm that combines binary-search exploration, lower-envelope pricing, and two complementary restart mechanisms. It achieves regret $O((\sqrt{TV}+1)\log T)$. With heterogeneous contexts, a new geometric difficulty arises: small feature changes can leave a relaxed feasible set narrow but far from the current feature vector. To address this difficulty, we introduce a multiscale shallow-pricing algorithm that maintains relaxed feasible sets and ellipsoidal approximations at several variation scales. Larger scales provide reliable localization certificates, while the smallest active scale determines the exploitation price. The algorithm achieves dynamic regret $O((d^2+d^{3/2}\sqrt{TV}){\log }^{2}T)$. Both guarantees match the identical-context lower bound $\Omega (\sqrt{TV}+\log \log T)$ up to logarithmic factors.