Diversified Recommendations for Agents with Adaptive Preferences

William Brown, Arpit Agarwal

Executive Summary Recommendation algorithms do more than just satisfy our current tastes—they actively shape our future preferences. This paper tackles the familiar "rabbit hole" phenomenon by developing a rigorous mathematical framework for managing this feedback loop. The authors introduce a no-regret algorithm achieving $\tilde{O}(T^{3/4})$ regret for recommendation systems where user preferences evolve based on past consumption. By identifying a class of "locally learnable" preference models and utilizing a novel "Robust Contracting" optimization technique, the research demonstrates that it is possible to maximize rewards while strictly maintaining content diversity.

1. Introduction and Problem Statement

Most recommendation algorithms assume user preferences are static or change independently of the system's actions. In reality, content consumption is a feedback loop: the more niche content an agent consumes, the more they might prefer it. This dynamic can lead to echo chambers, polarization, or decreased overall platform utility.

The challenge for a Recommender is twofold:

  1. The Moving Target: As an Agent consumes items, their "memory vector" (a histogram of past choices) shifts, altering their future selection probabilities.
  2. The Diversity Constraint: Platforms often want to ensure a "high entropy" (diverse) distribution of consumed items to avoid negative feedback loops and maintain a healthy content ecosystem.

Standard "bandit" algorithms, which learn by trial and error, fail in this setting. An action taken today might move the user into a state where they are impossible to "pull back" from a specific content niche.

2. Theoretical Framework and Methodology

The authors formalize this problem as an adversarial bandit task with a diversity constraint. Because this is a theoretical paper focused on algorithmic bounds and mathematical proofs, it relies on synthetic mathematical constructions rather than empirical datasets to prove lower bounds and demonstrate the "rabbit hole" effect.

Key Innovations

  • Everywhere Instantaneously Realizable Distributions (EIRD): The authors define a "safe" set of item distributions that can be induced by the Recommender regardless of the Agent's current memory. This set becomes the benchmark for evaluating performance.
  • Local Learnability: Because shifting an Agent’s memory is a slow and cumulative process, the Recommender cannot easily explore the entire preference space. The paper identifies classes of functions that can be learned entirely by observing the Agent’s behavior in a small, local region near the "uniform" memory state.
  • Robust Contracting FKM (RC-FKM): The authors modify the classic Flaxman-Kalai-McMahan (FKM) algorithm to handle "contracting" decision sets. As the Recommender learns more about the Agent's history, the set of feasible diverse distributions might shrink or shift. RC-FKM allows the system to optimize rewards while staying within these shifting boundaries.

3. Key Insights

  • Diversity as a Tool for Tractability: One of the most striking insights is that diversity constraints are not just a "social good"—they actually make the mathematics tractable. By forcing the system to stay away from extreme rabbit holes, the Recommender remains in a region of the preference space that is easier to model and control.
  • The "Local" Necessity: The authors prove a "Query Learning Lower Bound," showing that if a preference model is not locally learnable (i.e., if you have to move the user to extreme states to understand their tastes), any learning algorithm will take exponentially long to converge.
  • Realizability vs. Entropy: There is a deep connection between high-entropy (diverse) distributions and "realizability." If a preference model is sufficiently "dispersed" (meaning the user has at least a tiny probability of picking any item in a menu), then any sufficiently diverse distribution can be achieved from any history.

4. Main Results

  • Regret Bound: The proposed algorithm achieves $\tilde{O}(T^{3/4})$ regret against the best distribution in the EIRD set. This means that as time ($T$) progresses, the average loss compared to an optimal strategy that knows the user's preferences perfectly approaches zero.
  • Identified Learnable Classes: The paper proves that several complex preference models are locally learnable, including bounded-degree univariate and multivariate polynomials, as well as functions with a sparse Fourier basis (which are useful for capturing cyclical preferences).
  • Negative Results: The authors demonstrate that without their specific assumptions (such as dispersion), no algorithm can achieve sublinear regret, thereby justifying the necessity of their framework.

5. Limitations and Future Work

  • The $T^{3/4}$ Rate: While sublinear, this rate is slower than the $T^{1/2}$ or $T^{2/3}$ rates often seen in simpler bandit problems. Future work could investigate whether this is the optimal theoretical limit for this setting.
  • Single Agent Focus: The model currently evaluates one Recommender interacting with one Agent. In real-world scenarios, platforms deal with millions of agents whose preferences might be correlated (e.g., collaborative filtering).
  • Dispersion Assumption: The algorithm requires that users always have a non-zero (even if small) chance of picking any item in a menu. If a user completely "blocks out" certain content types, the current model may struggle to adapt.
  • Computational Complexity: Representing the EIRD set explicitly can be computationally expensive. The authors suggest developing more efficient characterizations of these sets as a promising path forward.

Summary updated

Abstract

When an Agent visits a platform recommending a menu of content to select from, their choice of item depends not only on immutable preferences, but also on their prior engagements with the platform. The Recommender's primary objective is typically to encourage content consumption which optimizes some reward, such as ad revenue, but they often additionally aim to ensure that a sufficiently wide variety of content is consumed by the Agent over time. We formalize this problem as an adversarial bandit task. At each step, the Recommender presents a menu of $k$ (out of $n$) items to the Agent, who selects one item in the menu according to their unknown {\it preference model}, which maps their history of past items to relative selection probabilities. The Recommender then observes the Agent's selected item and receives bandit feedback of the item's (adversarial) reward. In addition to optimizing reward from the selected items at each step, the Recommender must also ensure that the total distribution of chosen items has sufficiently high entropy. We define a class of preference models which are {\it locally learnable}, i.e.\ behavior over the entire domain can be estimated by only observing behavior in a small region; this includes models representable by bounded-degree polynomials as well as functions with a sparse Fourier basis. For this class, we give an algorithm for the Recommender which obtains $\tilde{O}(T^{3/4})$ regret against all item distributions satisfying two conditions: they are sufficiently diversified, and they are {\it instantaneously realizable} at any history by some distribution over menus. We show that these conditions are closely connected: all sufficiently high-entropy distributions are instantaneously realizable at any history of selected items. We also give a set of negative results justifying our assumptions, in the form of a runtime lower bound for non-local learning and linear regret lower bounds for alternate benchmarks.
BibTeX
@inproceedings{brown2022diversified,
  author = {William Brown and Arpit Agarwal},
  title = {{Diversified Recommendations for Agents with Adaptive Preferences}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=VVsNTPK1FBp},
}
Figure