# Incrementality Bidding via Reinforcement Learning under Mixed and Delayed Rewards

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 38 references that are in the map.
- First posted on arXiv 2 Jun 2022.

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [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)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Learning Adversarial Markov Decision Processes with Delayed Feedback](https://mlsanity.com/paper/2012.14843/) (2020)
- [Contextual Bandits with Cross-learning](https://mlsanity.com/paper/1809.09582/) (2018)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [Learning in repeated auctions](https://mlsanity.com/paper/2011.09365/) (2020)
- [Bid Prediction in Repeated Auctions with Learning](https://mlsanity.com/paper/2007.13193/) (2020)
- [Modeling Perception Errors towards Robust Decision Making in Autonomous Vehicles](https://mlsanity.com/paper/2001.11695/) (2020)
- [Handling many conversions per click in modeling delayed feedback](https://mlsanity.com/paper/2101.02284/) (2021)

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

- [Offline Reinforcement Learning for Optimizing Production Bidding Policies](https://mlsanity.com/paper/2310.09426/) (2023)
- [The (Marginal) Value of a Search Ad: An Online Causal Framework for Repeated Second-price Auctions](https://mlsanity.com/paper/2605.01756/) (2026)
- [Large-Scale Auto-bidding with Nash Equilibrium Constraints](https://mlsanity.com/paper/2503.10304/) (2025)
- [Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewards](https://mlsanity.com/paper/2510.20055/) (2025)
- [Learning to Bid in Repeated Second-Price Auctions with Dynamic Values and Aggregated Feedback](https://mlsanity.com/paper/2605.28133/) (2026)

## Abstract (arXiv)

Incrementality, which is used to measure the causal effect of showing an ad to a potential customer (e.g. a user in an internet platform) versus not, is a central object for advertisers in online advertising platforms. This paper investigates the problem of how an advertiser can learn to optimize the bidding sequence in an online manner without knowing the incrementality parameters in advance. We formulate the offline version of this problem as a specially structured episodic Markov Decision Process (MDP) and then, for its online learning counterpart, propose a novel reinforcement learning (RL) algorithm with regret at most widetildeO(H2√T), which depends on the number of rounds H and number of episodes T, but does not depend on the number of actions (i.e., possible bids). A fundamental difference between our learning problem from standard RL problems is that the realized reward feedback from conversion incrementality is mixed and delayed. To handle this difficulty we propose and analyze a novel pairwise moment-matching algorithm to learn the conversion incrementality, which we believe is of independent of interest.