Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewards
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Models ad bidding as a contextual MDP with delayed Poisson rewards and proposes a two-stage MLE with data splitting plus an RL algorithm achieving Õ(dH²√T) regret, validated by simulations.
Problem
Ad bidding must account for delayed and long-term ad effects, cumulative effects (reinforcement or fatigue), and customer heterogeneity, but prior work handles these only separately and lacks theoretical guarantees for jointly modeling them.
Approach
Model auto-bidding as a contextual MDP whose states encode recent ad exposure history and whose Poisson conversion rewards depend on customer context; estimate instantaneous effects with online Newton/CRTM and delayed effects with a two-stage MLE using data splitting so estimation errors do not feed back, then run optimistic RL within confidence sets.
Key results
- Proposed algorithm reaches fitted regret order 0.37 over T=20,000 while aggressive, random, and passive baselines all show linear regret (order 1.0).
- Theoretical regret bound Õ(dH²√T) with probability 1-δ for δ ≥ 6/T³.
- TS-MLE delayed-effect estimation error bounded by Õ(1/√N) with N the number of relevant observations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive contextual reinforcement learning instead of aggressive bidding | Ad bidding · Simulation, T=20000 | cumulative regret: 9568 [4991, 14146] -> 8525 [5649, 11401] | Helped |
| Use adaptive contextual reinforcement learning instead of random bidding | Ad bidding · Simulation, T=20000 | cumulative regret: 76945 [71390, 82500] -> 8525 [5649, 11401] | Helped |
| Use adaptive contextual reinforcement learning instead of passive bidding | Ad bidding · Simulation, T=20000 | cumulative regret: 184873 [135414, 234332] -> 8525 [5649, 11401] | Helped |
| Use adaptive contextual reinforcement learning instead of fixed baseline policies | Ad bidding · Simulation | fitted regret order: 0.37 vs 1.0 | Helped |
Surprising findings
- Aggressive bidding achieves lower cumulative regret than the proposed algorithm at small horizons (e.g., 228 vs 1770 at t=500), since the simulated reward decays rapidly.
Limitations
- Linear parameterization of expected conversion rate; neural extension lacks theoretical guarantees.
- No real-world or public advertising dataset experiments; only simulations.
- Budget constraints not handled.
Experimental setup
Datasets: simulated second-price auction data
Benchmarks: simulated second-price auction environment
Metrics: cumulative regret fitted regret order (log-log slope)
Baselines: aggressive bidding random bidding passive bidding
Builds on: contextual Markov decision process confidence region with truncated mean elliptical potential lemma
Closest papers by meaning
- Incrementality Bidding via Reinforcement Learning under Mixed and Delayed Rewards (NeurIPS 2022 · similarity 0.89)
- AuctionNet: A Novel Benchmark for Decision-Making in Large-Scale Games (NeurIPS 2024 · similarity 0.85)
- Online Learning of Delayed Choices (NeurIPS 2024 · similarity 0.85)
- Maximizing the Success Probability of Policy Allocations in Online Systems (AAAI 2024 · similarity 0.85)
- GenAuction: A Generative Auction for Online Advertising (AAAI 2025 · similarity 0.84)
- LLM-Auction: Generative Auction towards LLM-Native Advertising (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.