Incentivized Exploration with Stochastic Covariates: A Two-Stage Mechanism Design for Recommender System

Recommender systems play a crucial role in internet economies by connecting users with relevant products. However, designing effective recommender systems faces the key challenges: the exploration-exploitation tradeoff in securing incentive to explore new products against user’s self-interested preferences. While prior work addresses Bayesian Incentive Compatibility (BIC) in fixed-design linear bandits (Sellke & Slivkins, 2023), we tackle the challenge of stochastic user covariates sampled online. Unlike standard black-box reductions (Mansour et al., 2020), our two-stage framework exploits the linear reward structure to achieve sublinear regret while satisfying incentive constraints. To address it, we propose a two-stage algorithm that integrates incentivized exploration with any efficient plug-in offline learning algorithms. In the first stage, it explores products while maintaining incentive compatibility to gather optimal samples. The second stage employs inverse proportional gap sampling strategy (IPGS) integrated with any efficient learning methods to secure sublinear regret. Theoretically, we prove that algorithm RCB achieves $O(\sqrt{KdT})$ regret and simultaneously satisfies incentive constraints, and discovers the tradeoff between incentive budget and regret, validating in experiments. We demonstrate RCB’s strong incentive gain, sublinear regret, and robustness through a real application on personalized warfarin dosing and simulations.

(Problem) Recommendation systems must occasionally try unfamiliar options to discover what works best for each user, but users act in their own interest—they will ignore a suggestion that does not appear beneficial to them, making experimentation ineffective. This tension between learning and user trust is especially hard when every user is different and arrives with unique characteristics the system must handle on the fly. (Solution) We develop a two-stage algorithm that first explores new options while guaranteeing every recommendation remains credibly in the user's best interest, and then efficiently focuses on the most uncertain options to rapidly improve recommendation quality. Our mathematical analysis shows the algorithm's mistakes diminish over time and reveals a precise tradeoff: a larger persuasion budget accelerates learning but with diminishing returns. (Impact) This framework enables recommendation systems—including safety-critical applications like personalized medicine—to learn effectively without misleading users, building both trust and performance over time.