Truthful Bandit Mechanisms for Repeated Two-stage Ad Auctions

Online advertising platforms leverage a two-stage auction architecture to deliver personalized ads to users with low latency. The first stage efficiently selects a small subset of promising candidates out of the complete pool of ads. In the second stage, an auction is conducted within the subset to determine the winning ad for display, using click-through-rate predictions from the second-stage machine learning model. In this work, we investigate the online learning process of the first-stage subset selection policy, while ensuring game-theoretic properties in repeated two-stage ad auctions. Specifically, we model the problem as designing a combinatorial bandit mechanism with a general reward function, as well as additional requirements of truthfulness and individual rationality (IR). We establish an Ω(𝑇 ) regret lower bound for truthful bandit mechanisms, which demonstrates the challenge of simultaneously achieving allocation efficiency and truthfulness. To circumvent this impossibility result, we introduce truthful 𝛼-approximation oracles and evaluate the bandit mechanism through 𝛼-approximation regret. Two mechanisms are proposed, both of which are ex-post truthful and ex-post IR. The first mechanism is an explore-then-commit mechanism with regret 𝑂 (𝑇 2/3 ), and the second mechanism achieves an improved 𝑂 (log𝑇 /Δ 2 𝜙 ) regret where Δ 𝜙 is a distribution-dependent gap, but requires additional assumptions on the oracles and information about the strategic bidders.