Designing Truthful Contextual Multi-Armed Bandits based Sponsored Search Auctions
This work addresses the challenge of efficient and truthful ad selection in online advertising platforms, which is incremental as it improves upon prior methods with high regret.
The paper tackles the problem of designing truthful contextual multi-armed bandit auctions for sponsored search, where the platform must learn click-through rates from user contexts while eliciting private values from advertisers, and it addresses the impracticality of existing solutions that suffer from high regret of O(T^{2/3}).
For sponsored search auctions, we consider contextual multi-armed bandit problem in the presence of strategic agents. In this setting, at each round, an advertising platform (center) runs an auction to select the best-suited ads relevant to the query posted by the user. It is in the best interest of the center to select an ad that has a high expected value (i.e., probability of getting a click $\times$ value it derives from a click of the ad). The probability of getting a click (CTR) is unknown to the center and depends on the user's profile (context) posting the query. Further, the value derived for a click is the private information to the advertiser and thus needs to be elicited truthfully. The existing solution in this setting is not practical as it suffers from very high regret ($O(T^{\frac{2}{3}})$).