TL;DR
This paper introduces two novel algorithms, ARP and MARP, designed for recommender systems where users (agents) are "myopic"—meaning they will only follow a recommendation if they believe it serves their immediate self-interest. By strategically pooling recommendations for new products with those for established ones, the authors demonstrate how platforms can incentivize exploration, achieve optimal long-term performance (regret), and maintain fairness for returning users.
What Problem Does This Paper Address?
In modern two-sided markets like Uber, Instagram, or Amazon, platforms act as matchmakers between users and products. To improve, these platforms must explore: they need to recommend new or less-known "arms" (products/creators) to gather data. However, users are often myopic; they have an "opportunity cost" (time or money) and will ignore a recommendation if they suspect the platform is just using them as a guinea pig to test a potentially bad product.
If users ignore these "exploration" recommendations, the platform suffers from biased data and the "cold-start" problem, where new, high-quality creators never get the visibility they deserve. The challenge is to design a system that satisfies the incentive constraint: the user's expected reward from following a recommendation must be at least as high as their opportunity cost.
Methods
The authors model the system as a multi-agent bandit problem and propose two primary algorithms:
- Adaptive Recommendation Policy (ARP): Used when the platform knows the users' opportunity costs. It uses a "randomized pooling" strategy. The platform identifies a genuinely good "exploit" arm and an "unknown" arm. It then recommends one of these two based on a specific probability. Because the user doesn't know which arm is which, but knows the platform's overall "credibility," they are incentivized to follow the recommendation even if it might be the unknown arm.
- Modified Adaptive Recommendation Policy (MARP): Designed for more complex scenarios where user opportunity costs are private and unknown. Unlike ARP, which pools two arms, MARP pools recommendations across all arms and uses each arm's cumulative loss as feedback to adjust recommendation probabilities over time.
Key Innovations: * Transparent Mechanisms: The platform shares the reward history of recommendations but keeps the specific identities of the arms hidden to maintain the "pooling" effect. * Ex-Post Fairness: A new criterion ensuring that, over time, the proportion of "bad" recommendations a specific user receives doesn't exceed their personal tolerance level. * Adaptive Exploration: The exploration rate isn't fixed; it dynamically adjusts based on historical rewards to maximize the platform's "exploration capacity" without breaking user trust.
Datasets
The researchers evaluated their algorithms using both synthetic simulations and real-world data:
- Synthetic Benchmarks: They tested against Gaussian, Beta, and Bernoulli reward distributions to simulate various market conditions and "cold-start" severities.
- Criteo Uplift Prediction Dataset: A massive real-world dataset containing 25 million samples. The authors used this to construct a Bernoulli uplifting bandit, partitioning samples into 20 clusters (arms) to test how ARP and MARP handle real-world user features and outcomes.
Key Insights and Ideas
- Credibility as a Resource: The platform's ability to explore is limited by its historical performance. By recommending known-good products, the platform builds "credibility," which it then "spends" to get users to try new things.
- Information Asymmetry is a Feature, Not a Bug: By disclosing reward history but not arm identities, the platform creates a "rational belief" in the user that the current recommendation is likely to be good, even if it's an exploration arm.
- Fairness Protects the User Side: While most bandit fairness literature focuses on not discriminating against arms (products), this paper introduces ex-post fairness to protect agents (users) from being over-exploited for the sake of the platform's learning.
Key Results
- Asymptotic Optimality: Both ARP and MARP achieve sublinear regret, meaning that as time goes on, the platform's performance gets closer and closer to an omniscient strategy that always knows the best arm.
- Outperforming Standard Bandits: In simulations, standard algorithms like UCB (Upper Confidence Bound) and Thompson Sampling often failed because they ignored user incentives. When a standard algorithm recommended an arm below a user's opportunity cost, the user simply didn't pull it, stalling the platform's learning. ARP and MARP consistently maintained lower regret by keeping users "in the loop."
- Robustness: In the Criteo dataset tests, ARP and MARP were significantly more robust to high opportunity costs than traditional elimination algorithms, which tended to stop exploring prematurely.
Limitations and Future Work
- Contextual Bandits: The current model assumes a shared reward distribution for arms. The authors suggest extending this to contextual bandits, where recommendations are tailored to individual user demographics and tastes (e.g., Netflix-style personalization).
- Clinical Trials: An intriguing future application is in Adaptive Clinical Trials (ACT). Here, managing the "beliefs" and incentives of patients and doctors to stay in a trial as treatment protocols change is a critical, high-stakes version of the incentive problem.
- Strategic Opportunity Costs: The paper assumes opportunity costs are either known or drawn from a distribution; future work could explore users who strategically misreport their costs to get better recommendations.
Summary updated