# Learning the Optimal Recommendation from Explorative Users

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 34 references that are in the map.
- First posted on arXiv 6 Oct 2021.

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem](https://mlsanity.com/paper/1506.02550/) (2015)
- [Bayesian Exploration: Incentivizing Exploration in Bayesian Games](https://mlsanity.com/paper/1602.07570/) (2016)
- [Economic Recommendation Systems](https://mlsanity.com/paper/1507.07191/) (2015)
- [Rationally Inattentive Inverse Reinforcement Learning Explains YouTube Commenting Behavior](https://mlsanity.com/paper/1910.11703/) (2019)

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

- [Competing for Shareable Arms in Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2305.19158/) (2023)
- [Learning from a Learning User for Optimal Recommendations](https://mlsanity.com/paper/2202.01879/) (2022)
- [Learning from Imperfect Human Feedback: a Tale from Corruption-Robust Dueling](https://mlsanity.com/paper/2405.11204/) (2024)

## Abstract (arXiv)

We propose a new problem setting to study the sequential interactions between a recommender system and a user. Instead of assuming the user is omniscient, static, and explicit, as the classical practice does, we sketch a more realistic user behavior model, under which the user: 1) rejects recommendations if they are clearly worse than others; 2) updates her utility estimation based on rewards from her accepted recommendations; 3) withholds realized rewards from the system. We formulate the interactions between the system and such an explorative user in a K-armed bandit framework and study the problem of learning the optimal recommendation on the system side. We show that efficient system learning is still possible but is more difficult. In particular, the system can identify the best arm with probability at least 1-δ within O(1/δ) interactions, and we prove this is tight. Our finding contrasts the result for the problem of best arm identification with fixed confidence, in which the best arm can be identified with probability 1-δ within O(log(1/δ)) interactions. This gap illustrates the inevitable cost the system has to pay when it learns from an explorative user's revealed preferences on its recommendations rather than from the realized rewards.