# Semi-overlapping Multi-bandit Best Arm Identification for Sequential Support Network Learning

arXiv: https://arxiv.org/abs/2512.24959 · HTML: https://mlsanity.com/paper/2512.24959/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 76 references that are in the map.
- First posted on arXiv 31 Dec 2025.

## Builds on (most cited first, 30 of 35)

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Which Tasks Should Be Learned Together in Multi-task Learning?](https://mlsanity.com/paper/1905.07553/) (2019)
- [Data Selection for Language Models via Importance Resampling](https://mlsanity.com/paper/2302.03169/) (2023)
- [Efficiently Identifying Task Groupings for Multi-Task Learning](https://mlsanity.com/paper/2109.04617/) (2021)
- [Client-Edge-Cloud Hierarchical Federated Learning](https://mlsanity.com/paper/1905.06641/) (2019)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [A Survey on Negative Transfer](https://mlsanity.com/paper/2009.00909/) (2020)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [Do Current Multi-Task Optimization Methods in Deep Learning Even Help?](https://mlsanity.com/paper/2209.11379/) (2022)
- [Towards a Standardised Performance Evaluation Protocol for Cooperative MARL](https://mlsanity.com/paper/2209.10485/) (2022)
- [Optimality and Stability in Federated Learning: A Game-theoretic Approach](https://mlsanity.com/paper/2106.09580/) (2021)
- [Game of Gradients: Mitigating Irrelevant Clients in Federated Learning](https://mlsanity.com/paper/2110.12257/) (2021)
- [BenchMARL: Benchmarking Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2312.01472/) (2023)
- [Top-k Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/1905.12624/) (2019)
- [ForkMerge: Mitigating Negative Transfer in Auxiliary-Task Learning](https://mlsanity.com/paper/2301.12618/) (2023)
- [Auxiliary Task Reweighting for Minimum-data Learning](https://mlsanity.com/paper/2010.08244/) (2020)
- [Fairness in Federated Learning via Core-Stability](https://mlsanity.com/paper/2211.02091/) (2022)
- [Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm](https://mlsanity.com/paper/1301.6696/) (2013)
- [AutoSeM: Automatic Task Selection and Mixing in Multi-Task Learning](https://mlsanity.com/paper/1904.04153/) (2019)
- [Context-Aware Online Client Selection for Hierarchical Federated Learning](https://mlsanity.com/paper/2112.00925/) (2021)
- [Multi-Task Learning with Labeled and Unlabeled Tasks](https://mlsanity.com/paper/1602.06518/) (2016)
- [PGFed: Personalize Each Client's Global Objective for Federated Learning](https://mlsanity.com/paper/2212.01448/) (2022)
- [Compositional federated learning: Applications in distributionally robust averaging and meta learning](https://mlsanity.com/paper/2106.11264/) (2021)
- [AANG: Automating Auxiliary Learning](https://mlsanity.com/paper/2205.14082/) (2022)
- [Free-Rider and Conflict Aware Collaboration Formation for Cross-Silo Federated Learning](https://mlsanity.com/paper/2410.19321/) (2024)
- [Client Selection for Generalization in Accelerated Federated Learning: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/2303.10373/) (2023)
- [Federated Compositional Deep AUC Maximization](https://mlsanity.com/paper/2304.10101/) (2023)
- [Multi-task Representation Learning for Pure Exploration in Linear Bandits](https://mlsanity.com/paper/2302.04441/) (2023)
- [Multi-task Representation Learning for Pure Exploration in Bilinear Bandits](https://mlsanity.com/paper/2311.00327/) (2023)
- [Multitask Learning with No Regret: from Improved Confidence Bounds to Active Learning](https://mlsanity.com/paper/2308.01744/) (2023)

## Abstract (arXiv)

Many modern AI and ML problems require evaluating partners' contributions through shared yet asymmetric, computationally intensive processes and the simultaneous selection of the most beneficial candidates. Sequential approaches to these problems can be unified under a new framework, Sequential Support Network Learning (SSNL), in which the goal is to select the most beneficial candidate set of partners for all participants using trials; that is, to learn a directed graph that represents the highest-performing contributions. We demonstrate that a new pure-exploration model, the semi-overlapping multi-(multi-armed) bandit (SOMMAB), in which a single evaluation provides distinct feedback to multiple bandits due to structural overlap among their arms, can be used to learn a support network from sparse candidate lists efficiently. We develop a generalized GapE algorithm for SOMMABs and derive new exponential error bounds that improve the best known constant in the exponent for multi-bandit best-arm identification. The bounds scale linearly with the degree of overlap, revealing significant sample-complexity gains arising from shared evaluations. From an application point of view, this work provides a theoretical foundation and improved performance guarantees for sequential learning tools for identifying support networks from sparse candidates in multiple learning problems, such as in multi-task learning (MTL), auxiliary task learning (ATL), federated learning (FL), and in multi-agent systems (MAS).