# Truthful mechanisms for linear bandit games with private contexts

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 27 references that are in the map.
- First posted on arXiv 7 Jan 2025.

## Builds on (most cited first, 11 of 11)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [Bayesian Exploration: Incentivizing Exploration in Bayesian Games](https://mlsanity.com/paper/1602.07570/) (2016)
- [The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity](https://mlsanity.com/paper/2002.00558/) (2020)
- [Incentivizing Exploration with Selective Data Disclosure](https://mlsanity.com/paper/1811.06026/) (2018)
- [BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits](https://mlsanity.com/paper/1602.02196/) (2016)
- [Exploration and Incentives in Reinforcement Learning](https://mlsanity.com/paper/2103.00360/) (2021)

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

- [COBRA: Contextual Bandit Algorithm for Ensuring Truthful Strategic Agents](https://mlsanity.com/paper/2505.23720/) (2025)

## Abstract (arXiv)

The contextual bandit problem, where agents arrive sequentially with personal contexts and the system adapts its arm allocation decisions accordingly, has recently garnered increasing attention for enabling more personalized outcomes. However, in many healthcare and recommendation applications, agents have private profiles and may misreport their contexts to gain from the system. For example, in adaptive clinical trials, where hospitals sequentially recruit volunteers to test multiple new treatments and adjust plans based on volunteers' reported profiles such as symptoms and interim data, participants may misreport severe side effects like allergy and nausea to avoid perceived suboptimal treatments. We are the first to study this issue of private context misreporting in a stochastic contextual bandit game between the system and non-repeated agents. We show that traditional low-regret algorithms, such as UCB family algorithms and Thompson sampling, fail to ensure truthful reporting and can result in linear regret in the worst case, while traditional truthful algorithms like explore-then-commit (ETC) and ε-greedy algorithm incur sublinear but high regret. We propose a mechanism that uses a linear program to ensure truthfulness while minimizing deviation from Thompson sampling, yielding an O(ln T) frequentist regret. Our numerical experiments further demonstrate strong performance in multiple contexts and across other distribution families.