# Learning to Bid Without Knowing your Value

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2017.

## Built on by (most cited first, 30 of 34)

- [Stochastic Bandits for Multi-platform Budget Optimization in Online Advertising](https://mlsanity.com/paper/2103.10246/) (2021)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [Online Bidding Algorithms for Return-on-Spend Constrained Advertisers](https://mlsanity.com/paper/2208.13713/) (2022)
- [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023)
- [Beyond Bandit Feedback in Online Multiclass Classification](https://mlsanity.com/paper/2106.03596/) (2021)
- [Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions](https://mlsanity.com/paper/2110.03906/) (2021)
- [Offline Reinforcement Learning for Optimizing Production Bidding Policies](https://mlsanity.com/paper/2310.09426/) (2023)
- [Fast Rate Learning in Stochastic First Price Bidding](https://mlsanity.com/paper/2107.01835/) (2021)
- [No-Regret Learning in Partially-Informed Auctions](https://mlsanity.com/paper/2202.10606/) (2022)
- [Learning to Incentivize Information Acquisition: Proper Scoring Rules Meet Principal-Agent Model](https://mlsanity.com/paper/2303.08613/) (2023)
- [Adversarial Constrained Bidding via Minimax Regret Optimization with Causality-Aware Reinforcement Learning](https://mlsanity.com/paper/2306.07106/) (2023)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Joint Value Estimation and Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2502.17292/) (2025)
- [Incrementality Bidding via Reinforcement Learning under Mixed and Delayed Rewards](https://mlsanity.com/paper/2206.01293/) (2022)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [Selling Joint Ads: A Regret Minimization Perspective](https://mlsanity.com/paper/2409.07819/) (2024)
- [Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality](https://mlsanity.com/paper/2406.19824/) (2024)
- [Adaptive maximization of social welfare](https://mlsanity.com/paper/2310.09597/) (2023)
- [Improved learning rates in multi-unit uniform price auctions](https://mlsanity.com/paper/2501.10181/) (2025)
- [Online Bidding under RoS Constraints without Knowing the Value](https://mlsanity.com/paper/2503.03195/) (2025)
- [The (Marginal) Value of a Search Ad: An Online Causal Framework for Repeated Second-price Auctions](https://mlsanity.com/paper/2605.01756/) (2026)
- [Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty](https://mlsanity.com/paper/2302.09700/) (2023)
- [Dynamic Reinsurance Treaty Bidding via Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2506.13113/) (2025)
- [Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization](https://mlsanity.com/paper/2510.19591/) (2025)
- [Profit Maximization in Bilateral Trade against a Smooth Adversary](https://mlsanity.com/paper/2605.12664/) (2026)
- [Bandits for Sponsored Search Auctions under Unknown Valuation Model: Case Study in E-Commerce Advertising](https://mlsanity.com/paper/2304.00999/) (2023)
- [No Bidding, No Regret: Pairwise-Feedback Mechanisms for Digital Goods and Data Auctions](https://mlsanity.com/paper/2306.01860/) (2023)
- [Advancing Ad Auction Realism: Practical Insights & Modeling Implications](https://mlsanity.com/paper/2307.11732/) (2023)
- [Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition](https://mlsanity.com/paper/2505.17379/) (2025)
- [Auto-bidding under Return-on-Spend Constraints with Uncertainty Quantification](https://mlsanity.com/paper/2509.16324/) (2025)

## Abstract (arXiv)

We address online learning in complex auction settings, such as sponsored search auctions, where the value of the bidder is unknown to her, evolving in an arbitrary manner and observed only if the bidder wins an allocation. We leverage the structure of the utility of the bidder and the partial feedback that bidders typically receive in auctions, in order to provide algorithms with regret rates against the best fixed bid in hindsight, that are exponentially faster in convergence in terms of dependence on the action space, than what would have been derived by applying a generic bandit algorithm and almost equivalent to what would have been achieved in the full information setting. Our results are enabled by analyzing a new online learning setting with outcome-based feedback, which generalizes learning with feedback graphs. We provide an online learning algorithm for this setting, of independent interest, with regret that grows only logarithmically with the number of actions and linearly only in the number of potential outcomes (the latter being very small in most auction settings). Last but not least, we show that our algorithm outperforms the bandit approach experimentally and that this performance is robust to dropping some of our theoretical assumptions or introducing noise in the feedback that the bidder receives.