Contextual Bandit with Herding Effects: Algorithms and Recommendation Applications

Luyue Xu, Liming Wang, Hong Xie, Mingqiang ZhouarXiv 2024 · OpenReview

Abstract

Contextual bandits serve as a fundamental algorithmic framework for optimizing recommendation decisions online. Though extensive attention has been paid to tailoring contextual bandits for recommendation applications, the "herding effects" in user feedback have been ignored. These herding effects bias user feedback toward historical ratings, breaking down the assumption of unbiased feedback inherent in contextual bandits. This paper develops a novel variant of the contextual bandit that is tailored to address the feedback bias caused by the herding effects. A user feedback model is formulated to capture this feedback bias. We design the TS-Conf (Thompson Sampling under Conformity) algorithm, which employs posterior sampling to balance the exploration and exploitation tradeoff. We prove an upper bound for the regret of the algorithm, revealing the impact of herding effects on learning speed. Extensive experiments on datasets demonstrate that TS-Conf outperforms four benchmark algorithms. Analysis reveals that TS-Conf effectively mitigates the negative impact of herding effects, resulting in faster learning and improved recommendation accuracy.

Introduction

Standard recommendation algorithms assume user ratings reflect pure preference, but in reality, users are often swayed by what others think—a phenomenon called the "herding effect." Contextual bandits, the backbone of modern recommendation systems, typically learn to suggest items by balancing exploration and exploitation under the assumption that user feedback is unbiased. However, in the real world, historical ratings act as a confounder. For instance, a high average rating for a movie makes a user more likely to rate it highly themselves, regardless of their internal preference. Ignoring this bias leads to "spurious correlations," suboptimal recommendations, and slow convergence.

Methodology

The authors propose a mathematical framework to decouple true preference from social conformity:

  1. User Feedback Model: A user's rating is modeled as a weighted linear combination of conformity (leaning toward historical averages), true preference (match between user taste and item features), and random noise.
  2. TS-Conf Algorithm: "Thompson Sampling under Conformity" uses posterior sampling to manage the exploration-exploitation tradeoff. Since the conformity factor and preference vector are intertwined, exact calculation is computationally expensive.
  3. TS-ConfMCMC: To ensure practicality, a three-stage Gibbs sampler (a type of Markov Chain Monte Carlo method) is employed to efficiently estimate the posterior distributions of user preferences despite the herding bias.

Experimental Evaluation

The approach was evaluated using four large-scale real-world datasets: Amazon Music, MovieLens, Yelp, and Google Maps. Synthetic datasets were also used to stress-test the algorithm under controlled noise and dimensionality.

Key Results and Analysis

The experiments demonstrate that TS-Conf effectively mitigates the negative impact of herding effects.

  • Superior Accuracy: Across all real-world datasets, TS-Conf consistently achieved the lowest cumulative regret compared to benchmarks like LinUCB.
  • MCMC Efficiency: The TS-ConfMCMC approximation performs nearly as well as exact sampling with limited iterations, making it viable for real-time applications.
  • Impact of Dimensionality: As shown in the figure below, the algorithm maintains sublinear regret across various feature dimensions ($d=5$ to $d=20$). While stronger herding effects can slow down learning, TS-Conf still significantly outperforms traditional bandits that ignore this bias.
Cumulative regret across different dimensions (d=5 to d=20) comparing TS-Conf and TS-ConfMCMC variants.

Conclusion

This work highlights the importance of accounting for social bias in recommendation systems. By explicitly modeling the herding effect, the TS-Conf algorithm achieves faster learning and improved accuracy. Future work may explore non-linear herding models and dynamic conformity factors that change over time or across different item categories.

Summary updated

Abstract

Contextual bandits serve as a fundamental algorithmic framework for optimizing recommendation decisions online. Though extensive attention has been paid to tailoring contextual bandits for recommendation applications, the "herding effects" in user feedback have been ignored. These herding effects bias user feedback toward historical ratings, breaking down the assumption of unbiased feedback inherent in contextual bandits. This paper develops a novel variant of the contextual bandit that is tailored to address the feedback bias caused by the herding effects. A user feedback model is formulated to capture this feedback bias. We design the TS-Conf (Thompson Sampling under Conformity) algorithm, which employs posterior sampling to balance the exploration and exploitation tradeoff. We prove an upper bound for the regret of the algorithm, revealing the impact of herding effects on learning speed. Extensive experiments on datasets demonstrate that TS-Conf outperforms four benchmark algorithms. Analysis reveals that TS-Conf effectively mitigates the negative impact of herding effects, resulting in faster learning and improved recommendation accuracy.
BibTeX
@misc{xu2024contextual,
  author = {Luyue Xu and Liming Wang and Hong Xie and Mingqiang Zhou},
  title = {{Contextual Bandit with Herding Effects: Algorithms and Recommendation Applications}},
  year = {2024},
  eprint = {2408.14432},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.14432},
}
Figure