TL;DR
This paper introduces the Multiple Plays Bandit (MPB) algorithm, which uses a single bandit instance to manage multiple recommendations simultaneously, significantly speeding up learning compared to existing methods that use one instance per recommendation. MPB achieves comparable or better click-through rates, especially when paired with the UCB1 bandit algorithm, offering a more efficient approach to personalized recommendations.
What Problem Does This Paper Address?
Recommender systems (RS) are ubiquitous, helping users discover relevant items. A key challenge in RS is the "exploration-exploitation dilemma": balancing showing users items they are likely to enjoy (exploitation) with discovering new items that might be even better (exploration). This is particularly complex in "multiple-play" scenarios where the system needs to recommend several items at once. Traditional bandit algorithms, designed for recommending a single item, are often adapted by running multiple independent instances, one for each item to be recommended. This approach, however, can be inefficient, leading to slower learning and potentially higher user abandonment rates. The authors aim to improve the learning efficiency and reduce abandonment in multiple-play recommendation systems.
Methods
The core innovation is the Multiple Plays Bandit (MPB) algorithm. Unlike prior methods like Ranked Bandits Algorithm (RBA) and Independent Bandits Algorithm (IBA) that use m separate bandit instances for m recommendations, MPB uses a single bandit instance.
Here's how it works:
- Simultaneous Recommendation: MPB recommends a list of m items at each time step.
- Single Bandit Instance: A single bandit algorithm (e.g., UCB1 or e-greedy) manages the selection of all m items.
- Sequential Selection: The first item is selected based on the bandit's strategy. Subsequent items are selected sequentially from the remaining available items, considering the choices already made for that time step.
- Reward Mechanism: The reward system is designed to encourage diversity. If the user clicks the first recommended item, the reward is +1. If the user clicks any other item in the list, the reward is 0. If no item is clicked, the reward is -1. This negative reward for non-clicked items penalizes less relevant items more effectively.
- Efficient Learning: By using a single instance, MPB updates its estimates for m items simultaneously, leading to faster convergence and improved learning speed.
Datasets
The authors evaluate their approach using two standard benchmark datasets:
- MovieLens-100: Contains 943 users who rated 100 movies on a scale of 1 to 5.
- Jester: Contains 25,000 users who rated 100 jokes on a scale of -10 to 10.
For evaluation, they define "click" based on relevance thresholds:
- MovieLens: Ratings > 2 (or > 4) are considered clicks.
- Jester: Ratings > 7 are considered clicks.
Key Insights and Ideas
- Single Instance Efficiency: The core insight is that a single bandit instance can learn more effectively by observing multiple user interactions (clicks/non-clicks) per time step, rather than relying on multiple independent instances that learn in isolation.
- Diversity Encouragement: The negative reward for non-clicked items, especially when the first item isn't clicked, implicitly encourages the system to explore and recommend a diverse set of items, which is crucial for user satisfaction and reducing abandonment.
- UCB1 Synergy: The MPB approach shows a particularly strong synergy with the UCB1 bandit algorithm, leading to substantial improvements in learning speed. This suggests that UCB1's optimistic exploration strategy benefits greatly from the richer feedback provided by MPB.
- e-greedy Limitations: While MPB improves learning speed with UCB1, the benefits are less pronounced with the e-greedy algorithm. This is attributed to e-greedy's random exploration, which might not fully leverage the multiple feedback signals provided by MPB.
Key Results
- Speedup: When using the UCB1 bandit algorithm, MPB achieves learning speeds up to thirteen times faster than existing methods (RBA and IBA) on the MovieLens dataset with a relevance threshold of 2.
- Abandonment Rates: MPB achieves abandonment rates comparable to or better than RBA and IBA, especially in the long run.
- e-greedy Performance: With the e-greedy algorithm, MPB shows equivalent abandonment rates to state-of-the-art methods, but the speedup is less dramatic.
- Dataset Performance: The improvements are observed across both MovieLens and Jester datasets, indicating the generalizability of the MPB approach.
- Statistical Significance: The learning speed improvements with MPB and UCB1 were statistically significant, confirmed by Wilcoxon tests.
Limitations and Future Work
- e-greedy Performance: The paper notes that MPB does not significantly improve learning speed when paired with the e-greedy algorithm, and IBA remains faster in some scenarios. The authors suggest the random nature of e-greedy might be a factor.
- Reward Value Tuning: The choice of -1 for non-clicked items is arbitrary. Future work could explore adjusting this negative reward value.
- Contextual Bandits: The current MPB approach does not consider user or item context. Future work could explore extending MPB to contextual bandit settings for more personalized recommendations.
- Theoretical Guarantees: The authors aim to develop a version of UCB1 with stronger theoretical guarantees for handling multiple simultaneous plays.
Summary updated