Abstract
Contextual bandit algorithms are essential for modern recommendation systems but typically rely on flat feature vectors, which fail to capture the complex relationships inherent in many real-world domains. We present Relational Boosted Bandits (RB2), a framework that integrates Statistical Relational Learning with the exploration-exploitation paradigm. RB2 utilizes gradient-boosted relational regression trees and a novel informed sampling strategy to handle structured data directly. Our evaluation across multiple real-world datasets demonstrates that RB2 significantly outperforms standard propositional and non-exploratory relational baselines in terms of cumulative regret and interpretability.
1. Introduction
Modern recommendation engines and online advertising platforms rely heavily on contextual bandits to balance exploration and exploitation. However, these models generally assume context is representable as a flat feature vector. In relational domains like social networks or biological systems, entities are defined by their interactions and links. Flattening such data into sparse matrices often leads to information loss and computational inefficiency. Relational Boosted Bandits (RB2) addresses this by reasoning over objects and their links directly using first-order logic.
2. Methodology
RB2 combines the expressiveness of relational models with the efficiency of gradient boosting.
- Relational Regression Trees (RRTGB): The base learner uses first-order logic predicates to split nodes, allowing the model to capture non-linear symbolic logic.
- Online Mini-Batch Boosting: To adapt boosting for online settings, RB2 updates the ensemble in mini-batches, adding sets of trees as new data arrives.
- Informed Sampling: Instead of uniform sampling, RB2 prioritizes "hard" examples—positive samples with low predicted probability and negative samples with high predicted probability. This stochastic prioritization prevents overfitting to simple patterns.
- Action Selection and Explainability: RB2 employs a Softmax strategy for action selection. For interpretability, the boosted ensemble can be distilled into a single, human-readable Relational Regression Tree.
3. Experimental Evaluation
The framework was tested on one synthetic and five real-world datasets: IMDB (actor-director links), MovieLens (genre prediction), ICML Co-Author (collaboration prediction), Drug Interaction (DDI), and NELL-Sports (team-sport links).
4. Results and Discussion
RB2 consistently demonstrates superior performance compared to Batch RRTGB (no exploration) and Epsilon-Greedy RRTGB. As shown in the regret curves, RB2 achieves significantly lower cumulative regret, particularly in complex domains like ICML Co-Author and NELL-Sports.
A key finding is the advantage of relational representations over propositional ones. In head-to-head tests on the IMDB dataset, RB2 outperformed LinUCB, illustrating that linear models struggle with the high-dimensional, sparse nature of flattened relational data. Furthermore, the informed sampling strategy proved essential for rapid convergence to an accurate policy.
5. Conclusion
RB2 represents a significant step forward in contextual bandits for structured data. By leveraging relational boosting and informed sampling, it provides a robust, interpretable, and high-performing solution for complex real-world tasks. Future work will explore active learning integration and further refinements to the interpretability of tree ensembles.
Summary updated