Relational Boosted Bandits

Ashutosh Kakadiya, Sriraam Natarajan, Balaraman Ravindran

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).

Cumulative regret curves for MovieLens (d), ICML Co-Author (e), and NELL-Sports (f) datasets.

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.

Cumulative regret curves for IMDB (a), Simulated Movie (b), and DDI (c) datasets.

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

Abstract

Contextual bandits algorithms have become essential in real-world user interaction problems in recent years. However, these algorithms rely on context as attribute value representation, which makes them unfeasible for real-world domains like social networks are inherently relational. We propose Relational Boosted Bandits(RB2), acontextual bandits algorithm for relational domains based on (relational) boosted trees. RB2 enables us to learn interpretable and explainable models due to the more descriptive nature of the relational representation. We empirically demonstrate the effectiveness and interpretability of RB2 on tasks such as link prediction, relational classification, and recommendations.
BibTeX
@inproceedings{kakadiya2021relational,
  author = {Ashutosh Kakadiya and Sriraam Natarajan and Balaraman Ravindran},
  title = {{Relational Boosted Bandits}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17439},
}
Figure