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

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 66 references that are in the map.
- First posted on arXiv 4 Jun 2024.

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

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Deep & Cross Network for Ad Click Predictions](https://mlsanity.com/paper/1708.05123/) (2017)
- [TALLRec: An Effective and Efficient Tuning Framework to Align Large Language Model with Recommendation](https://mlsanity.com/paper/2305.00447/) (2023)
- [Deep Learning Recommendation Model for Personalization and Recommendation Systems](https://mlsanity.com/paper/1906.00091/) (2019)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Actions Speak Louder than Words: Trillion-Parameter Sequential Transducers for Generative Recommendations](https://mlsanity.com/paper/2402.17152/) (2024)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Statistical Inference of the Value Function for Reinforcement Learning in Infinite Horizon Settings](https://mlsanity.com/paper/2001.04515/) (2020)
- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [Anytime-valid off-policy inference for contextual bandits](https://mlsanity.com/paper/2210.10768/) (2022)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity](https://mlsanity.com/paper/2002.00558/) (2020)
- [Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2108.03706/) (2021)
- [Regret Bounds for Information-Directed Reinforcement Learning](https://mlsanity.com/paper/2206.04640/) (2022)
- [Online Forgetting Process for Linear Regression Models](https://mlsanity.com/paper/2012.01668/) (2020)
- [Statistical Inference for Online Decision-Making: In a Contextual Bandit Setting](https://mlsanity.com/paper/2010.07283/) (2020)
- [An elementary analysis of ridge regression with random design](https://mlsanity.com/paper/2203.08564/) (2022)
- [Residual Bootstrap Exploration for Bandit Algorithms](https://mlsanity.com/paper/2002.08436/) (2020)
- [Incentivizing Combinatorial Bandit Exploration](https://mlsanity.com/paper/2206.00494/) (2022)
- [Residual Bootstrap Exploration for Stochastic Linear Bandit](https://mlsanity.com/paper/2202.11474/) (2022)
- [Online Regularization towards Always-Valid High-Dimensional Dynamic Pricing](https://mlsanity.com/paper/2007.02470/) (2020)
- [Incentive-Aware Recommender Systems in Two-Sided Markets](https://mlsanity.com/paper/2211.15381/) (2022)
- [Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints](https://mlsanity.com/paper/2301.10230/) (2023)
- [Incentivizing Exploration with Linear Contexts and Combinatorial Actions](https://mlsanity.com/paper/2306.01990/) (2023)
- [Incentivized Exploration via Filtered Posterior Sampling](https://mlsanity.com/paper/2402.13338/) (2024)

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

- [Advancing Retail Data Science: Comprehensive Evaluation of Synthetic Data](https://mlsanity.com/paper/2406.13130/) (2024)

## Abstract (arXiv)

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(√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.