Abstract
The linear submodular bandit problem addresses the dual challenge of diversified retrieval and online learning in recommendation systems. While offline submodular maximization is well-studied, online learning under complex, intersecting constraints—such as multiple knapsacks and $k$-systems—remains difficult. This paper introduces AFSM-UCB, an algorithm that adaptively switches between standard and density-based Upper Confidence Bounds (UCB). AFSM-UCB achieves theoretical approximation guarantees matching fast offline algorithms and demonstrates superior performance over traditional greedy baselines in real-world tasks.
Introduction
Modern recommendation systems must balance item quality with diversity. Submodular functions effectively model this "diminishing returns" property, where the marginal utility of an item decreases as the set of selected items grows. However, real-world applications often impose complex constraints:
- Knapsack Constraints: Limitations on resources like user time or budget (e.g., a user only has 30 minutes to consume content).
- $k$-system Constraints: Structural rules governing item selection (e.g., "no more than 2 sports articles" and "at least one local news item").
Existing bandit algorithms often struggle when these constraints intersect, frequently suffering from "linear regret"—meaning they never stop making significant mistakes. This work bridges the gap by providing a robust framework for learning under multiple, overlapping constraints.
The AFSM-UCB Algorithm
The proposed AFSM-UCB (Adaptively Focuses on a Standard or Modified UCB) algorithm employs a two-layered approach to handle uncertainty and constraints simultaneously:
- Dual UCB Scores: It maintains a "Standard UCB" for estimated rewards and a "Modified UCB" for reward-to-cost ratios. The modified version is essential for knapsack constraints, ensuring the algorithm picks items with the "most bang for the buck."
- Multi-Threshold Strategy: Instead of a simple greedy selection, the algorithm iterates through multiple density thresholds. For each threshold, it generates a candidate set using a greedy sub-algorithm (GM-UCB).
- Selection: The final recommendation list is the candidate set with the highest total Standard UCB score.
This approach prevents the algorithm from being trapped by locally optimal but globally poor greedy choices, a common failure mode in constrained environments.
Experimental Evaluation
The researchers evaluated AFSM-UCB on three environments: a Synthetic News dataset, MovieLens 100K, and the Million Song Dataset. These benchmarks represent varying levels of constraint complexity and data sparsity.
As shown in the results, AFSM-UCB (the proposed method) consistently outperforms baselines like LSBGreedy and CGreedy. The performance gap is particularly pronounced as the budget or cardinality increases, where the adaptive thresholding strategy allows for more efficient exploration of the solution space compared to standard greedy methods.
Key Insights
A critical finding is that standard greedy methods fail when faced with complex intersecting constraints. AFSM-UCB avoids this by prioritizing "density"—the marginal gain per unit of cost. Furthermore, a filtering condition ensures that items are only selected if they provide significant value relative to both the current set and the empty set, mitigating the impact of early-stage uncertainty.
The robustness of the method is evident across different parameter settings. Even when constraints are tight, AFSM-UCB maintains a sub-linear regret growth ($O(\sqrt{T})$), which is the gold standard for bandit algorithms. This indicates that the algorithm successfully learns the underlying reward function while respecting all operational constraints.
Conclusion and Future Work
AFSM-UCB provides a significant advancement in online submodular maximization. By integrating density-based filtering with a multi-threshold greedy approach, it handles intersecting constraints that defeat simpler algorithms. While the multi-threshold approach is more computationally intensive than a single greedy pass, its theoretical alignment with the best offline algorithms makes it a powerful tool for complex recommendation tasks. Future work includes extending this framework to "full bandit" feedback scenarios and optimizing the computational overhead for high-throughput production environments.
Summary updated