# No-Regret Learning in Partially-Informed Auctions

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 39 references that are in the map.
- First posted on arXiv 22 Feb 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015)
- [Learning to Bid Without Knowing your Value](https://mlsanity.com/paper/1711.01333/) (2017)

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

- [Learning to Incentivize Information Acquisition: Proper Scoring Rules Meet Principal-Agent Model](https://mlsanity.com/paper/2303.08613/) (2023)
- [A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Design](https://mlsanity.com/paper/2210.10278/) (2022)
- [Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learners](https://mlsanity.com/paper/2502.08597/) (2025)
- [Learn then Decide: A Learning Approach for Designing Data Marketplaces](https://mlsanity.com/paper/2503.10773/) (2025)
- [Profit Maximization in Bilateral Trade against a Smooth Adversary](https://mlsanity.com/paper/2605.12664/) (2026)
- [No Bidding, No Regret: Pairwise-Feedback Mechanisms for Digital Goods and Data Auctions](https://mlsanity.com/paper/2306.01860/) (2023)
- [Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition](https://mlsanity.com/paper/2505.17379/) (2025)

## Abstract (arXiv)

Auctions with partially-revealed information about items are broadly employed in real-world applications, but the underlying mechanisms have limited theoretical support. In this work, we study a machine learning formulation of these types of mechanisms, presenting algorithms that are no-regret from the buyer's perspective. Specifically, a buyer who wishes to maximize his utility interacts repeatedly with a platform over a series of T rounds. In each round, a new item is drawn from an unknown distribution and the platform publishes a price together with incomplete, "masked" information about the item. The buyer then decides whether to purchase the item. We formalize this problem as an online learning task where the goal is to have low regret with respect to a myopic oracle that has perfect knowledge of the distribution over items and the seller's masking function. When the distribution over items is known to the buyer and the mask is a SimHash function mapping ℝd to 0,1ℓ, our algorithm has regret tilde O((Tdℓ)1/2). In a fully agnostic setting when the mask is an arbitrary function mapping to a set of size n and the prices are stochastic, our algorithm has regret tilde O((Tn)1/2).