Regret Minimization in Dynamic Pricing and Auctions

92 concepts82 papers1 proposal

In traditional economics, setting the optimal price for a good or a reserve price for an auction assumes that you know the underlying distribution of what buyers are willing to pay. In reality, sellers rarely have this luxury. Instead, they must learn consumer preferences on the fly through repeated interactions.

This creates a fundamental exploration-exploitation dilemma: price an item too high, and you lose the sale entirely; price it too low, and you leave money on the table. The research direction of online price discovery addresses this challenge by framing pricing and auction design as online learning problems, using the metric of regret minimization to measure how much revenue is lost while learning the market.

Learning from Binary and Censored Feedback

The core difficulty of online pricing is that the feedback loop is highly restricted. When a seller posts a price, the buyer provides a binary response: they either buy the item or walk away. This is known as revealed preference or censored feedback. If a customer buys an item at \$10, the seller only learns that the customer's valuation is *at least* \$10, not their exact willingness to pay.

Kareem Amin et al. formalized this problem in Online Learning and Profit Maximization from Revealed Preferences, demonstrating that a merchant can strategically probe consumer preferences to achieve a per-round regret that vanishes at a rate of $O(n^2/T)$. This proves that near-optimal pricing strategies can be learned efficiently through a finite sequence of price adjustments.

To accelerate this learning process, researchers have looked for ways to extract richer signals from each interaction. Onno Zoeter introduced a novel approach in Optimal and Robust Price Experimentation: Learning by Lottery by utilizing lotteries—where customers pay for a probability of receiving an item. By offering probabilistic choices, the seller can test multiple price points simultaneously, resolving demand uncertainty significantly faster than traditional censored price experiments.

Modern e-commerce platforms rarely price items in a vacuum; they use contextual pricing, where every customer and product comes with a set of features (e.g., user demographics, device type, historical behavior). The buyer's valuation is typically modeled as a function of these features, such as a linear combination $v = \theta \cdot x$, where $\theta$ is a hidden parameter vector representing how much the market values each feature.

Searching for the optimal $\theta$ in a high-dimensional space using only binary feedback is a massive challenge. Jon Schneider et al. solved this geometrically in Contextual Search via Intrinsic Volumes. By leveraging integral geometry, the authors developed algorithms that achieve a double-logarithmic regret bound relative to the time horizon $T$. Instead of slowly narrowing down the price, their framework cuts through the high-dimensional parameter space using geometric volumes, allowing the pricing strategy to converge to near-zero regret exponentially fast.

Even when features are selected by an adversary rather than a stable distribution, regret can be kept remarkably low. Jianyu Xu et al. showed in Logarithmic Regret in Feature-based Dynamic Pricing that it is possible to achieve an optimal $O(d \log T)$ regret bound under adversarial conditions. For broader linear valuation models, Matilde Tullii et al. (Improved Algorithms for Contextual Dynamic Pricing) proved that dynamic pricing algorithms can hit the minimax optimal regret bound of $T^{2/3}$, establishing the absolute theoretical limit for learning efficiency in these environments.

Discretization of Infinite Action Spaces

When moving from a single posted price to complex economic mechanisms—such as menus of lotteries, two-part tariffs, or continuous data pricing curves—the space of possible pricing strategies becomes infinite and highly irregular. Multi-armed bandit algorithms typically require a finite set of choices ("arms") to guarantee convergence.

To bridge this gap, researchers rely on revenue-preserving discretization. The core intuition is to partition an infinite space of mechanisms into a finite grid such that any point on the grid preserves a predictable fraction of the optimal revenue.

Maria Florina Balcan et al. applied this technique in New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs, effectively reducing the search for complex multi-item mechanisms to a classic "learning-from-experts" problem. This discretization allows standard online algorithms to achieve sublinear regret even when buyer valuations are completely adversarial and unpredictable. Similarly, Keran Chen leveraged novel discretization schemes in Learning to Price Homogeneous Data to compress the massive space of potential pricing curves, making dynamic revenue maximization viable in emerging data marketplaces.

Defeating Strategic Manipulation

A major complication in online learning for pricing is that buyers are often non-myopic—they are strategic agents who think about the future. If a buyer realizes that a seller is using an online learning algorithm to discover their willingness to pay, the buyer has a strong incentive to manipulate the system. They might intentionally refuse to buy an item at a high price today, accepting a short-term loss of utility to trick the algorithm into lowering prices tomorrow.

To prevent this manipulation, learning algorithms must decouple future prices from individual past actions. Jinyan Liu et al. achieved this in Learning Optimal Reserve Price against Non-myopic Bidders by injecting noise calibrated to differential privacy. By masking the impact of any single bid on future iterations, the algorithm ensures that a strategic bidder cannot reliably manipulate the seller's pricing trajectory, allowing the seller to achieve sub-linear regret even against adversarial manipulation.

[Strategic Bidder] ---> [Individual Bid] ---\
                                             ---> [Differential Privacy Noise] ---> [Insulated Reserve Price]
[Strategic Bidder] ---> [Individual Bid] ---/

Alternatively, a seller can use aggressive pricing structures to force strategic buyers to reveal their true valuations. The authors of Reserve Pricing in Repeated Second-Price Auctions with Strategic Bidders introduced a "div-transformation" mechanism that isolates bidders one-by-one using exceptionally high "barrage" prices. This structural isolation neutralizes the long-term benefits of strategic underbidding, driving the strategic regret down to an ultra-fast $O(\log \log T)$ convergence rate.

Learning Under Budget and ROI Constraints

In modern digital advertising markets, the interaction is inverted: buyers (advertisers) use online learning algorithms to bid on items while managing strict internal constraints, such as fixed budgets or minimum Return-on-Investment (ROI) targets.

When both the seller and the buyer are adapting simultaneously, the system can easily become unstable. Negin Golrezaei et al. addressed this in Pricing against a Budget and ROI Constrained Buyer. They discovered that the seller's revenue function against an optimizing buyer follows a predictable, bell-shaped curve. By implementing an episodic binary search—where the seller holds prices constant for a block of rounds—the buyer's learning algorithm is given time to stabilize within each episode. This stabilization ensures that the seller's observations accurately reflect long-term market demand, yielding sublinear regret without needing to know the buyer's internal constraints.

From the buyer's perspective, managing these constraints requires local, adaptive rules. Jason Gaitonde et al. demonstrated in Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence that simple, gradient-based budget pacing algorithms allow individual advertisers to achieve sublinear regret. Crucially, the authors proved that even if the multi-agent market never settles into a stable Nash equilibrium, these pacing rules guarantee that the market captures at least 50% of the optimal social welfare, showing that local online learning naturally fosters global market efficiency.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_explore_then_exploit_pricing_39de87d9,
  title = {explore-then-exploit pricing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/explore-then-exploit-pricing/rdr_39de87d9044d475fabf928b650dae895},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_explore_then_exploit_pricing_39de87d9_v1,
  title = {explore-then-exploit pricing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/explore-then-exploit-pricing/rdr_39de87d9044d475fabf928b650dae895/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake