Preprint
Online Learning in Contextual Second-Price Pay-Per-Click Auctions
arXiv (Cornell University)
10/08/2023
DOI: 10.48550/arxiv.2310.05047
Abstract
We study online learning in contextual pay-per-click auctions where at each of the T rounds, the learner receives some context along with a set of ads and needs to make an estimate on their click-through rate (CTR) in order to run a second-price pay-per-click auction. The learner's goal is to minimize her regret, defined as the gap between her total revenue and that of an oracle strategy that always makes perfect CTR predictions. We first show that T−−√-regret is obtainable via a computationally inefficient algorithm and that it is unavoidable since our algorithm is no easier than the classical multi-armed bandit problem. A by-product of our results is a T−−√-regret bound for the simpler non-contextual setting, improving upon a recent work of [Feng et al., 2023] by removing the inverse CTR dependency that could be arbitrarily large. Then, borrowing ideas from recent advances on efficient contextual bandit algorithms, we develop two practically efficient contextual auction algorithms: the first one uses the exponential weight scheme with optimistic square errors and maintains the same T−−√-regret bound, while the second one reduces the problem to online regression via a simple epsilon-greedy strategy, albeit with a worse regret bound. Finally, we conduct experiments on a synthetic dataset to showcase the effectiveness and superior performance of our algorithms.
Details
- Title: Subtitle
- Online Learning in Contextual Second-Price Pay-Per-Click Auctions
- Creators
- Mengxiao ZhangHaipeng Luo
- Resource Type
- Preprint
- Publication Details
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2310.05047
- Language
- English
- Date posted
- 10/08/2023
- Academic Unit
- Business Analytics
- Record Identifier
- 9984701728002771
Metrics
1 Record Views