Incentivizing Exploration in Linear Contextual Bandits under Information Gap
Open Access
- 14 September 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 415-425
Abstract
Contextual bandit algorithms have been popularly used to address interactive recommendation, where the users are assumed to be cooperative to explore all recommendations from a system. In this paper, we relax this strong assumption and study the problem of incentivized exploration with myopic users, where the users are only interested in recommendations with their currently highest estimated reward. As a result, in order to obtain long-term optimality, the system needs to offer compensation to incentivize the users to take the exploratory recommendations. We consider a new and practically motivated setting where the context features employed by the user are more informative than those used by the system: for example, features based on users’ private information are not accessible by the system. We develop an effective solution for incentivized exploration under such an information gap, and prove that the method achieves a sublinear rate in both regret and compensation. We theoretically and empirically analyze the added compensation due to the information gap, compared with the case where the system has access to the same context features as the user does, i.e., without information gap. Moreover, we also provide a compensation lower bound of this problem.Keywords
All Related Versions
Funding Information
- Army Research Office (W911NF-23-1-0030)
- NSF (National Science Foundation) (2007492, 2128019, 1838615)
This publication has 17 references indexed in Scilit:
- Incentivizing exploration via information asymmetryXRDS: Crossroads, The ACM Magazine for Students, 2017
- Fairness Incentives for Myopic Agents2017
- Linear Thompson sampling revisitedElectronic Journal of Statistics, 2017
- Contextual Bandits in a Collaborative Environment2016
- Bayesian Incentive-Compatible Bandit Exploration2015
- Implementing the “Wisdom of the Crowd”Journal of Political Economy, 2014
- Incentivizing exploration2014
- Inferring the demographics of search users2013
- The demographics of web search2010
- A contextual-bandit approach to personalized news article recommendation2010