Abstract
The linear submodular bandit problem was proposed to simultaneously address diversified retrieval and online learning in a recommender system. If there is no uncertainty, this problem is equivalent to a submodular maximization problem under a cardinality constraint. However, in some situations, recommendation lists should satisfy additional constraints such as budget constraints, other than a cardinality constraint. Thus, motivated by diversified retrieval considering budget constraints, we introduce a submodular bandit problem under the intersection of $l$ knapsacks and a $k$-system constraint. Here $k$-system constraints form a very general class of constraints including cardinality constraints and the intersection of $k$ matroid constraints. To solve this problem, we propose a non-greedy algorithm that adaptively focuses on a standard or modified upper-confidence bound. We provide a high-probability upper bound of an approximation regret, where the approximation ratio matches that of a fast offline algorithm. Moreover, we perform experiments under various combinations of constraints using a synthetic and two real-world datasets and demonstrate that our proposed methods outperform the existing baselines.
Introduction
In modern interactive recommender systems, the goal is often to suggest a list of items that maximizes user satisfaction. To achieve this, systems must balance relevance with diversity—ensuring that a user isn't presented with five nearly identical news articles, for instance. This property of diminishing returns is mathematically captured by submodular functions. When the system must simultaneously learn user preferences through feedback, the challenge becomes a submodular bandit problem.
While previous research has explored this area, it often focused on simple constraints, such as a fixed list length (cardinality). Real-world scenarios are far more complex. A user might have a limited time budget (a knapsack constraint), or a platform might need to limit items from specific categories to maintain variety (a $k$-system constraint). This paper addresses the gap by formulating the problem under the intersection of multiple knapsacks and $k$-system constraints.
Addressing Complex Constraints
Traditional greedy algorithms, which perform well under simple constraints, often struggle when faced with multiple, overlapping restrictions. The authors demonstrate that in these complex settings, standard greedy approaches can become trapped in suboptimal choices, leading to linear regret.
As shown in the comparison above, existing methods like LSBGreedy and CGreedy are limited to specific constraint types. The proposed method is the first to provide a unified framework that handles cardinality, knapsack, and $k$-system constraints simultaneously.
The AFSM-UCB Algorithm
To overcome the limitations of greedy methods, the authors propose AFSM-UCB (Adaptively Focuses on a Standard or Modified Upper Confidence Bound). This algorithm utilizes a non-greedy thresholding approach inspired by offline submodular maximization.
Instead of simply picking the item with the highest Upper Confidence Bound (UCB) score, AFSM-UCB employs a filtering mechanism:
- Thresholding: It only considers items whose modified UCB scores (UCB divided by cost) exceed a specific threshold $\rho$.
- Adaptive Search: Since the optimal threshold is unknown, the algorithm searches over a grid of possible values for $\rho$.
- Selection: It generates candidate lists for each threshold and selects the one with the highest overall UCB score.
This approach prevents short-sighted choices by balancing the raw value of an item against its cost and its impact on the remaining budget and constraints.
Key Insights and Results
The research provides both strong theoretical guarantees and empirical evidence of the algorithm's effectiveness:
- Theoretical Robustness: AFSM-UCB achieves an $\alpha$-approximation regret bound of $O(\sqrt{mT \ln(mT/\delta)})$. Remarkably, its approximation ratio matches that of the best-known "fast" offline algorithms, which operate with full knowledge of the reward function.
- Empirical Superiority: The algorithm was tested on three datasets: a synthetic news environment, MovieLens100K (incorporating genre and popularity constraints), and the Million Song Dataset (using actual song lengths as a knapsack constraint). In all cases, AFSM-UCB consistently outperformed baselines like LSBGreedy and CGreedy.
- Versatility: Even in scenarios where constraints were relaxed and greedy algorithms typically perform well, AFSM-UCB remained competitive, proving it is a robust choice for both simple and complex environments.
Conclusion
By introducing a non-greedy, threshold-based approach to the submodular bandit problem, this work provides a powerful tool for building more realistic and constrained recommender systems. Future work aims to extend these findings to the "full bandit" setting, where the system only observes the aggregate reward of a list rather than individual item feedback, presenting an even greater challenge for online learning.
Summary updated