# Designing Truthful Contextual Multi-Armed Bandits based Sponsored Search Auctions

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2020.

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

- [Repeated Principal-Agent Games with Unobserved Agent Rewards and Perfect-Knowledge Agents](https://mlsanity.com/paper/2304.07407/) (2023)
- [Estimating and Incentivizing Imperfect-Knowledge Agents with Hidden Rewards](https://mlsanity.com/paper/2308.06717/) (2023)
- [A Multi-Arm Bandit Approach To Subset Selection Under Constraints](https://mlsanity.com/paper/2102.04824/) (2021)
- [Fairness and Privacy Guarantees in Federated Contextual Bandits](https://mlsanity.com/paper/2402.03531/) (2024)
- [Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits](https://mlsanity.com/paper/2402.05575/) (2024)
- [Minimax PAC Bounds for Learning in Exogenous Contextual MDPs](https://mlsanity.com/paper/2606.25170/) (2026)
- [Contextual Procurement Auctions with Bandit Learning](https://mlsanity.com/paper/2607.05813/) (2026)

## Abstract (arXiv)

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 × 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^frac23)).