# Bandit Sequential Posted Pricing via Half-Concavity

arXiv: https://arxiv.org/abs/2312.12794 · HTML: https://mlsanity.com/paper/2312.12794/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 47 references that are in the map.
- First posted on arXiv 20 Dec 2023.

## Builds on (most cited first, 24 of 24)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Learning Simple Auctions](https://mlsanity.com/paper/1604.03171/) (2016)
- [Dynamic Pricing with Finitely Many Unknown Valuations](https://mlsanity.com/paper/1807.03288/) (2018)
- [Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem](https://mlsanity.com/paper/1911.11936/) (2019)
- [The Sample Complexity of Auctions with Side Information](https://mlsanity.com/paper/1511.02296/) (2015)
- [Learning Multi-item Auctions with (or without) Samples](https://mlsanity.com/paper/1709.00228/) (2017)
- [The Sample Complexity of Up-to-varepsilon Multi-Dimensional Revenue Maximization](https://mlsanity.com/paper/1808.02458/) (2018)
- [Making the Most of Your Samples](https://mlsanity.com/paper/1407.2479/) (2014)
- [Ironing in the Dark](https://mlsanity.com/paper/1511.06918/) (2015)
- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Pricing Query Complexity of Revenue Maximization](https://mlsanity.com/paper/2111.03158/) (2021)
- [Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments](https://mlsanity.com/paper/1610.09976/) (2016)
- [Learning Reserve Prices in Second-Price Auctions](https://mlsanity.com/paper/1912.10069/) (2019)
- [Learning with Comparison Feedback: Online Estimation of Sample Statistics](https://mlsanity.com/paper/2101.04176/) (2021)
- [Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms](https://mlsanity.com/paper/2111.03962/) (2021)
- [Description Complexity of Regular Distributions](https://mlsanity.com/paper/2305.05590/) (2023)
- [Non-Stochastic CDF Estimation Using Threshold Queries](https://mlsanity.com/paper/2301.05682/) (2023)

## Built on by (most cited first, 5 of 5)

- [Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond](https://mlsanity.com/paper/2503.01701/) (2025)
- [Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12903/) (2026)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)
- [Learning Markov Decision Processes under Fully Bandit Feedback](https://mlsanity.com/paper/2602.02260/) (2026)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)

## Abstract (arXiv)

Sequential posted pricing auctions are popular because of their simplicity in practice and their tractability in theory. A usual assumption in their study is that the Bayesian prior distributions of the buyers are known to the seller, while in reality these priors can only be accessed from historical data. To overcome this assumption, we study sequential posted pricing in the bandit learning model, where the seller interacts with n buyers over T rounds: In each round the seller posts n prices for the n buyers and the first buyer with a valuation higher than the price takes the item. The only feedback that the seller receives in each round is the revenue. Our main results obtain nearly-optimal regret bounds for single-item sequential posted pricing in the bandit learning model. In particular, we achieve an tildeO(mathsfpoly(n)√T) regret for buyers with (Myerson's) regular distributions and an tildeO(mathsfpoly(n)T^2/3) regret for buyers with general distributions, both of which are tight in the number of rounds T. Our result for regular distributions was previously not known even for the single-buyer setting and relies on a new half-concavity property of the revenue function in the value space. For n sequential buyers, our technique is to run a generalized single-buyer algorithm for all the buyers and to carefully bound the regret from the sub-optimal pricing of the suffix buyers.