CS Paper Radar

Optimal Contextual Pricing in Non-Stationary Environments

Yiding Feng, Alireza Rezaeimoghadam

cs.LG ·submitted 2026-10-29 10:48 UTC · v1
benchmarktheory

Abstract

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 periodic and inconsistency-triggered restarts. 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. We address this difficulty through a multiscale shallow-pricing algorithm that maintains relaxed feasible sets and enclosing ellipsoids 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)$, where $d$ is the context dimension. For fixed $d$, both guarantees match the lower bound $Ω(\sqrt{TV}+\log\log T)$ up to logarithmic factors in $T$, establishing near-optimality among deterministic algorithms for every $V\in[0,T]$, including the stationary case.

Closest papers

Nearest neighbours by meaning across the whole index.

SALE: Source-Aware Dynamic Pricing with Strategic Buyers

cs.LG stat.MLstat.ME ·2026-10-15 ·Jinjiang Zou, Yang Li, Zemin Zheng
similarity 0.72
Abstract · 60 pages, 9 figures

In modern commerce, firms and platforms typically use customer features from different sources to personalize prices: some features are verified using seller records or third-party data, while others are self-reported and may be strategically manipulated by buyers seeking lower prices. In this paper, we study the problem of source-aware dynamic pricing with strategic buyers, where the buyer's valuation is a sparse linear function of her high-dimensional features plus market noise with an unknown distribution. We develop the Source-Aware Localized exploration and calibrated Exploitation (SALE) policy, which personalizes exploration using past learning and verified features, and corrects for strategic manipulation using verified and reported features during exploitation. Our novel personalized design aims to narrow the range of prices explored, reducing unnecessary exploration at excessively high or low prices. To support learning under this design, we derive a new population equation that enables sparse valuation parameter estimation and, in turn, nonparametric estimation of the unknown noise distribution, even when buyer features are dependent over time. By uncovering the intrinsic sparse structure, our analysis establishes estimation guarantees for both learning tasks using the same exploration data. With these guarantees, we show that SALE achieves a sublinear expected regret bound, explicitly quantifying the benefit of using verified features to narrow exploration intervals. Several numerical studies further demonstrate the appealing performance of SALE.

0.33

Pricing Today, Shaping Tomorrow: Contextual Dynamic Pricing in Purchase-Driven Evolving Systems

cs.LG stat.MLstat.ME ·2026-10-31 ·Jinjiang Zou, Yang Li, Zemin Zheng
similarity 0.63
Abstract · 63 pages, 4 figures

Across diverse markets, it is important for firms to balance attracting customers with managing operational conditions, such as workloads and delivery times. Dynamic pricing plays a central role in this tradeoff, as the orders generated today can change the conditions faced by future customers. We develop a novel framework for contextual dynamic pricing with an observed shared state and unknown purchase-driven transitions. The valuation model allows unknown mean functions of customer covariates and state, unknown state-specific scales and a common unknown standardized noise distribution. We propose Shadow-Adjusted Pricing in Evolving Systems (SHAPE), which incorporates a purchase's future revenue consequences into current pricing. Purchase-shadow adjustment and scale standardization reveal a common one-dimensional oracle price map across states, allowing SHAPE to retain its pricing history across value updates without repeating coarse exploration. The same active sales records support price-map learning and joint updates of continuation values and purchase shadows, without fitting the noise distribution or full transition matrices. To support this reuse under purchase-driven feedback, we establish pricing guarantees for history-dependent inputs and stability bounds for the joint updates. Under regularity, coverage and design conditions, we obtain sublinear expected regret against a finite-horizon dynamic oracle for linear, Hölder and sparse linear mean models. For affine valuations at fixed state and feature dimensions, SHAPE matches the static semiparametric minimax time exponent up to logarithmic factors for every fixed noise-tail smoothness order $β\ge2$. Numerical experiments further demonstrate the appealing performance of SHAPE.

0.27

Contextual Search and Bilateral Trade with a Trace-Square-Root Potential

cs.GT cs.LG ·2026-11-06 ·Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme +1 more
similarity 0.63
Abstract

We present a unified potential method for contextual search and bilateral trade with one-bit feedback and obtain order-tight algorithms for both problems. Our framework starts from a Bayesian perspective in which the unknown target (for contextual search) and the unknown pair of valuations (for bilateral trade) are sampled from a known prior distribution. In that model, the decision maker bases its prediction on the posterior distribution, obtained by conditioning on feedback received in previous rounds. For Bayesian contextual search, we present an algorithm with a total loss bounded by $O(\mathrm{Tr} \sqrt Σ)$, where $Σ$ is the covariance matrix of the target's prior; and for contextual bilateral trade, our algorithm's regret is bounded by $O(\mathrm{Tr} \sqrt{Σ_S}+\mathrm{Tr} \sqrt{Σ_B})$, where $Σ_S$ and $Σ_B$ are the covariance matrices of the seller's and buyer's valuations. We then use ideas from this Bayesian setting and adapt a ``dual'' of this trace-square-root potential to the classical worst-case setting, where the target and valuations are chosen adversarially from the unit Euclidean ball. For both contextual search and bilateral trade, we obtain tight $O(\sqrt d)$-regret algorithms. These results match the existing lower bounds up to a constant factor and improve on the previous guarantees of $O(d\log d)$ for contextual search and of $O(d6^d)$ for bilateral trade.

0.11

Optimal Regret for Profit Maximization in Bilateral Trade

cs.GT cs.LG ·2026-11-06 ·Matteo Castiglioni, Anna Lunghi, Alberto Marchesi
theory similarity 0.62
Abstract

Learning to profit from trade requires learning both sides of a market: what a seller is willing to accept and what a buyer is willing to pay. We study repeated bilateral trade, where an intermediary posts a purchase price to a seller and a sale price to a buyer whose valuations are drawn from an unknown joint distribution. Trade occurs only if both parties accept their respective prices, in which case the intermediary earns the difference between the two prices. The intermediary observes only whether trade occurs, without observing either valuation. We show that learning both sides of the market is no harder, in terms of regret, than learning just one. Specifically, we design an algorithm achieving regret $\widetilde{\mathcal{O}}(T^{2/3})$ against the best fixed pair of prices, matching, up to logarithmic factors, the classical lower bound for one-dimensional dynamic pricing. Our result shows that the classical one-dimensional regret rate survives the transition to two dimensions, raising the question of whether this absence of a curse of dimensionality extends to arbitrarily high dimensions.

0.13

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

cs.DS stat.MLcs.LG ·2026-09-22 ·Shinsaku Sakaue
theoryhighly cited similarity 0.62
Abstract

We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the environment returns an action that maximizes the utility over the same set. When the utility vector and the actions lie in the $d$-dimensional Euclidean unit ball, we give a randomized algorithm whose regret---the cumulative utility shortfall relative to optimal actions---is $O(\sqrt d)$ in expectation for every time horizon, without knowledge of the horizon. The dependence on $d$ is optimal up to a constant factor by the known $Ω(\sqrt d)$ lower bound for horizons $T\ge d$. Our algorithm maintains matrix multiplicative weights on polynomial feature spaces at geometrically spaced scales. It selects a recommendation distribution by solving a linear program and updates its score matrices by comparing the available actions with the feedback action. With rational oracle outputs and feedback actions, an implementation computable relative to a linear-optimization oracle preserves the $O(\sqrt d)$ regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.

0.41

Computing Multi-Slot First-Price Pacing Equilibria at Scale via Entropic Smoothing

cs.GT math.OC ·2026-10-16 ·Yuchen Xie, Shenyinying Tu, Yuan Gao, Yi Zhang, Deepak Kumar
similarity 0.62
Abstract · 40 pages, 6 figures, 5 tables

Pacing equilibria describe how budget-constrained advertisers clear an ad market, but computing one at production scale is hard when every request fills several slots: the allocation jumps whenever two campaigns' scores cross. We consider the first-price pacing equilibrium (FPPE) of auctions with $K$ homogeneous slots and unit-demand campaigns, whose Eisenberg-Gale dual reduces, via a TopK identity, to a convex program over bids. Regularizing each request's allocation with the binary (Fermi-Dirac) entropy gives a smooth, strictly convex dual whose gradient is exactly spend minus budget and whose evaluation splits into independent one-dimensional threshold solves, one per request. The smoothed equilibrium converges to the hard one at an explicit $O(\sqrt{T})$ rate, and a duality gap certifies how far any bids are from the hard equilibrium. We implement an efficient multi-GPU solver and test it on a production ad workload. We use it to compute an equilibrium price anchor: each campaign's hindsight equilibrium cost per key result.

0.12

MemPrice: Online Memory Allocation via Adaptive Pricing for Long-Horizon Agents

cs.AI ·2026-10-18 ·Yiming Zong, Shiyuan Piao, Jiashuo Jiang, Fugee Tsung
benchmark similarity 0.61
Abstract

Long-horizon LLM agents face a fundamental allocation problem as interaction histories grow: which information to retain, how much context to devote to it, and at what granularity. Existing memory mechanisms largely focus on relevance, retrieval, or compression, leaving this allocation trade-off implicit. We introduce MemPrice, which treats active context as a shared resource and dynamically allocates it across memories and representation levels. MemPrice turns accumulated memory pressure into an adaptive price on context, encouraging detail only when its estimated retention value justifies the additional footprint. This pressure persists across memory refreshes, allowing the contents of memory to evolve while preserving long-run control over context usage. We show that irreversible compression can force linear worst-case regret against hindsight following its own memory trajectory, and introduce a same-state benchmark to evaluate allocation on MemPrice's realized memory states. MemPrice enforces the hard context budget at every round and regulates long-run occupancy through adaptive pricing, without prior knowledge of the interaction horizon. Under priced-frontier regularity, its average allocation-regret bound against this benchmark vanishes when accumulated estimation error is sublinear. We evaluate the framework under matched memory budgets on LongMemEval, LoCoMo, AppWorld, and WebShop across three foundation models, spanning both query-blind memory construction and goal-directed agent context management.

0.13

Inter-Temporal Price Constraints in Dynamic Pricing: Performance Guarantees Under Price Monotonicity and Promotion Fatigue

cs.DM math.OC ·2026-09-23 ·Weiyuan Li, Paat Rusmevichientong, Huseyin Topaloglu
similarity 0.61
Abstract · 31 pages in main text, 14 pages in appendix, 1 figure

We study dynamic pricing problems under inter-temporal price constraints. We have resources with limited capacities. At each time period, we decide which products to make available and what prices to charge for the available products. The sale probability for a product depends on its price. If we make a sale for a product, then we collect a revenue reflecting the price and consume the capacities of a combination of resources. We work with two types of inter-temporal constraints. In price monotonicity, the prices charged for a product at different time periods have to be monotone. In promotion fatigue, we can discount a product at most once over each time interval of a fixed length. Computing the optimal policy is intractable. We use fluid approximations to construct policies. Traditionally, policies from fluid approximations make randomized decisions at each time period by following an optimal solution to the fluid approximation, but such randomized decisions easily violate price monotonicity or promotion fatigue constraints. We develop policies that sample price paths according to an optimal solution to the fluid approximation, while satisfying the inter-temporal constraints. Letting $c_{\min}$ be the smallest initial capacity of a resource and $L$ be the maximum number of resources used by a product, our policies have a performance guarantee of $\max\Big\{ \frac{1}{8L}, \, \frac{1}{2} - \sqrt{\frac{\log c_{\min}}{2 \,c_{\min}}} - \frac{L}{c_{\min}}\Big\}$. Thus, under large resource capacities, our policies are guaranteed to obtain at least half of the optimal total expected revenue. The latter performance guarantee is tight in the sense that no policy can, in general, obtain more than half of the optimal objective value of the fluid approximation even under large resource capacities. We unify our approach to open the path for extensions to other inter-temporal price constraints.

0.31