Master-Slave Deep Architecture for Top-K Multiarmed Bandits With Nonlinear Bandit Feedback and Diversity Constraints

Hanchi Huang, Li Shen, Deheng Ye, Wei Liu

TL;DR

This paper introduces a novel "master-slave" deep learning architecture to tackle the challenging problem of Top-K combinatorial multi-armed bandits (CMAB) with non-linear feedback and diversity constraints. By employing a hierarchical approach with specialized "slave" models that learn from each other and a "master" model for decision-making, the proposed method significantly outperforms existing state-of-the-art algorithms in recommendation tasks.

What Problem Does This Paper Address?

Recommender systems often face the challenge of selecting a diverse set of items (Top-K) that not only satisfy user preferences (reward) but also adhere to certain constraints, such as item diversity. Traditional multi-armed bandit (MAB) frameworks, especially those with linear feedback, struggle to capture the complex, non-linear relationships between item selections and user satisfaction. Furthermore, the feedback received in real-world scenarios is often aggregated (bandit feedback), meaning we only know the overall outcome of a set of recommendations, not the individual contribution of each item. This paper addresses the gap in handling Top-K CMAB with non-linear bandit feedback and explicit diversity constraints, a setting that is more representative of real-world recommendation scenarios but significantly harder to solve.

Methods

The core of the proposed solution is a master-slave hierarchical architecture.

  • Master Model: This component acts as the feedback estimator and final decision-maker. It uses a Neural Contextual UCB-based network (NeuralUCB) to learn the non-linear feedback function from historical data. It then aggregates and evaluates "elite" samples provided by the slave models, using a composite score to select the best recommendation.
  • Slave Models: Six specialized "slave" models are designed to generate diverse and high-quality candidate solutions. Each slave has a unique strength:
  • Solver Sampler: Uses mathematical programming solvers (Gurobi) to find solutions that strictly satisfy diversity constraints, even if rewards are not optimal.
  • Primal-Dual Wolpertinger Sampler: Efficiently searches the combinatorial space and balances reward-constraint trade-offs using primal-dual methods.
  • G2ANet Sampler: Leverages graph attention networks to infer the influence of diversity constraints between pairs of items.
  • Improved CEM-PPO Sampler: An evolutionary algorithm that is computationally efficient and requires less back-propagation.
  • Teacher-Student Sampler: Promotes mutual learning among slave models to generate more diversified and elite samples.
  • Random Sampler: Used for initial exploration.
  • Co-training and Sample Sharing: To enhance the performance of the slave models, a policy co-training technique is employed, allowing them to learn from each other and avoid local optima. This includes learning from demonstrations and sharing elite samples.
  • Improved Gumbel Top-K Sampling: A differentiable sampling trick is integrated into some slave models to ensure end-to-end training.

Datasets

The paper evaluates its approach on:

  • Synthetic Datasets: Four synthetic datasets are generated with linear, quadratic, cubic, and mixed forms of reward functions to test the algorithms under controlled conditions.
  • Real-World Datasets: Four real-world datasets are used:
  • LastFM
    • Delicious
    • MovieLens
    • Yahoo!

These datasets are preprocessed to extract item feature vectors and construct user-item interaction logs.

Key Insights and Ideas

  • Master-Slave Synergy: The hierarchical master-slave architecture is crucial. The master's ability to estimate feedback and provide surrogate rewards, combined with the slaves' specialized exploration and constraint satisfaction capabilities, leads to superior performance.
  • Diversity is Key: Explicitly incorporating diversity constraints is not just an add-on but a necessity for realistic recommendation systems, and the proposed method effectively balances this with reward maximization.
  • Ensemble of Experts: Having multiple slave models, each with different strengths (constraint satisfaction, exploration, efficiency), creates a robust ensemble that covers various aspects of the complex problem.
  • Co-training Boosts Performance: The policy co-training mechanism among slave models is vital for preventing individual models from getting stuck in local optima and for improving the overall quality and diversity of generated samples.
  • Non-linear Feedback is Realistic: The assumption of non-linear bandit feedback is more aligned with real-world user behavior than simpler linear models.

Key Results

  • Superior Performance: The proposed master-slave algorithm consistently outperforms existing state-of-the-art methods (e.g., RLfD, Wolpertinger, CSAR-EST) across all synthetic and real-world datasets in terms of both reward (rt) and constraint violation rate (ct). For instance, on synthetic datasets, the master-slave algorithm achieved improvements of 8.24% to 17.88% in reward over the second-best method.
  • Effective Constraint Handling: The algorithm demonstrates a powerful ability to deal with diversity constraints, achieving significantly lower violation rates (e.g., 59.09% to 76.08% better than the second-best method on synthetic datasets).
  • Balanced Slave Contributions: The "average recommended rate" metric shows that while some slave models (like the solver and random samplers) become more dominant later, others contribute significantly in the early stages, highlighting the balanced nature of the ensemble.
  • Ablation Studies Confirm Design Choices: Experiments without specific slave models or without the co-training/replay buffer mechanisms show a noticeable drop in performance, validating the importance of each component.

Limitations and Future Work

  • Computational Cost: While effective, the master-slave architecture, especially with the G2ANet sampler, can be computationally intensive. The paper notes that interaction frequencies can be adjusted, and some samplers can be discarded if resources are limited.
  • Semantic Loss for Constraints: The authors acknowledge that while they explored semantic loss for constraint handling, they were unable to fully reproduce its effectiveness due to implementation errors and lack of domain knowledge. This is identified as a promising area for future work.
  • Top-K Off-Policy Correction: The paper mentions that adopting top-K off-policy correction and adversarial training could further improve the co-training of slave models.
  • Non-stationary Environments: The paper briefly discusses adapting the approach for non-stationary user feedback by combining NeuralUCB with discounted UCB, but a full exploration is left for future work.
  • Generalization to Other O-COPs: The paper suggests that the framework can be adapted for other combinatorial optimization problems like cascading bandits and GPS routing, but a thorough investigation is needed.

Summary updated

Abstract

We propose a novel master-slave architecture to solve the top-$K$ combinatorial multi-armed bandits problem with non-linear bandit feedback and diversity constraints, which, to the best of our knowledge, is the first combinatorial bandits setting considering diversity constraints under bandit feedback. Specifically, to efficiently explore the combinatorial and constrained action space, we introduce six slave models with distinguished merits to generate diversified samples well balancing rewards and constraints as well as efficiency. Moreover, we propose teacher learning based optimization and the policy co-training technique to boost the performance of the multiple slave models. The master model then collects the elite samples provided by the slave models and selects the best sample estimated by a neural contextual UCB-based network to make a decision with a trade-off between exploration and exploitation. Thanks to the elaborate design of slave models, the co-training mechanism among slave models, and the novel interactions between the master and slave models, our approach significantly surpasses existing state-of-the-art algorithms in both synthetic and real datasets for recommendation tasks. The code is available at: \url{https://github.com/huanghanchi/Master-slave-Algorithm-for-Top-K-Bandits}.
BibTeX
@article{huang2024master,
  author = {Hanchi Huang and Li Shen and Deheng Ye and Wei Liu},
  title = {{Master-Slave Deep Architecture for Top-K Multiarmed Bandits With Nonlinear Bandit Feedback and Diversity Constraints}},
  journal = {IEEE Trans. Neural Networks Learn. Syst.},
  year = {2024},
  doi = {10.1109/tnnls.2023.3306801},
}
Figure