# User Response in Ad Auctions: An MDP Formulation of Long-Term Revenue Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 49 references that are in the map.
- First posted on arXiv 16 Feb 2023.

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

- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Multi-Item Mechanisms without Item-Independence: Learnability via Robustness](https://mlsanity.com/paper/1911.02146/) (2019)
- [The Sample Complexity of Auctions with Side Information](https://mlsanity.com/paper/1511.02296/) (2015)
- [Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments](https://mlsanity.com/paper/1610.09976/) (2016)
- [A Field Guide to Personalized Reserve Prices](https://mlsanity.com/paper/1602.07720/) (2016)
- [Optimising Trade-offs Among Stakeholders in Ad Auctions](https://mlsanity.com/paper/1404.5127/) (2014)
- [Empirical Distribution of Equilibrium Play and Its Testing Application](https://mlsanity.com/paper/1310.7654/) (2013)

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

- [The Bidding Games: Reinforcement Learning for MEV Extraction on Polygon Blockchain](https://mlsanity.com/paper/2510.14642/) (2025)

## Abstract (arXiv)

We propose a new Markov Decision Process (MDP) model for ad auctions to capture the user response to the quality of ads, with the objective of maximizing the long-term discounted revenue. By incorporating user response, our model takes into consideration all three parties involved in the auction (advertiser, auctioneer, and user). The state of the user is modeled as a user-specific click-through rate (CTR) with the CTR changing in the next round according to the set of ads shown to the user in the current round. We characterize the optimal mechanism for this MDP as a Myerson's auction with a notion of modified virtual value, which relies on the value distribution of the advertiser, the current user state, and the future impact of showing the ad to the user. Leveraging this characterization, we design a sample-efficient and computationally-efficient algorithm which outputs an approximately optimal policy that requires only sample access to the true MDP and the value distributions of the bidders. Finally, we propose a simple mechanism built upon second price auctions with personalized reserve prices and show it can achieve a constant-factor approximation to the optimal long term discounted revenue.