Strategyproof algorithms in linear contextual bandits with private contexts

Contextual bandits have broad applications, including clinical trials and LLM routing. In a clinical trial, a doctor uses patients’ private information, such as symptoms and family history, to assign treatments and learn from observed outcomes. To improve overall patient welfare, the doctor may assign seemingly suboptimal treatments to some patients to reduce uncertainty, whereas individual patients seek to maximize their immediate outcomes. This misalignment may incentivize patients’ misreporting to avoid exploration, substantially biasing treatment-effect estimates and reducing long-term patient welfare. It is therefore important for bandit algorithms to be strategyproof, ensuring patients cannot benefit from misreporting their contexts. In this paper, we conduct a comprehensive study of strategyproof algorithms for linear bandits with private contexts. We first establish complementary gaps of classical strategyproof bandit algorithms. Explore-then-commit and truthful Thompson sampling either lack $O(\mathrm{polylog}T)$ problem-dependent regret guarantees or can incur linear problem-independent regret, while non-strategyproof algorithms such as LinUCB generally suffer linear regret in strategic settings. Secondly, we establish a novel minimax regret lower bound of $\Omega (T^{2/3})$ for strategyproof bandit algorithms, revealing the fundamental challenge posed by strategic misreporting. Motivated by this, we propose Confidence-Gated Truthful UCB (CGT-UCB), which first employs a confidence gate to construct a proposal policy that adaptively switches between greedy and optimistic policies for agents with different contexts. This mechanism avoids the excessive exploration induced by the standard optimism-in-the-face-of-uncertainty principle. CGT-UCB then feeds the proposal policy into a specially designed linear programming problem that enforces strategyproofness while balancing exploration and exploitation under strategyproofness. CGT-UCB simultaneously achieves \(O(T^2/3)\) problem-independent regret and \(O(polylog T)\) problem-dependent regret. Experiments on synthetic and real-world datasets support our theoretical findings and demonstrate the practical effectiveness of CGT-UCB.