Multi-Armed Bandits: Combinatorial, Dueling, and Multi-Agent
Principal Investigator: Vaneet Aggarwal
"Bandit" problems capture a basic trade-off: a system must keep choosing among options, learning only from the results of the choices it actually makes, while balancing trying new options against using the best one found so far. Examples include picking servers or network paths, recommending items, and choosing which subsets of items to test. Real problems add complications. Choices may be whole sets of items, feedback may be only a comparison ("A was better than B"), many agents may learn together, and the system may need to be fair or to tolerate failures.
This project develops bandit algorithms with proven performance in these settings. Performance is measured by "regret", how much worse the system does than if it had known the best choice from the start. Our outcomes include:
- Algorithms for choosing sets of items when the reward depends on the set in complex, non-linear ways, including fast top-K selection (DART) and greedy-style methods.
- Methods for many agents learning together with little communication, including in federated settings where data stays local.
- Learning from comparisons over continuous ranges of options ("dueling bandits").
- Efficient learning when the payoff is a smooth unknown function (Gaussian-process bandits), using bounded memory.
- Guarantees that every option gets a fair share at all times, and a framework that stays reliable when some components fail.
Representative Publications
Mridul Agarwal, Vaneet Aggarwal, Christopher J. Quinn, and Abhishek Umrawal, "DART: aDaptive Accept RejecT for non-linear top-K subset identification," in Proc. AAAI, Feb 2021.
Mridul Agarwal, Vaneet Aggarwal, Christopher J. Quinn, and Abhishek Umrawal, "Stochastic Combinatorial Bandits with Linear Space and Non-Linear Feedback," in Proc. ALT, Mar 2021.
Mridul Agarwal, Vaneet Aggarwal, and Kamyar Azizzadenesheli, "Multi-Agent Multi-Armed Bandits with Limited Communication," Journal of Machine Learning Research, Jul 2022.
Mridul Agarwal, Vaneet Aggarwal, Christopher J. Quinn, and Abhishek Umrawal, "Stochastic Top K-Subset Bandits with Linear Space and Non-Linear Feedback with Applications to Social Influence Maximization," ACM/IMS Transactions on Data Science, vol. 2, issue 4, Article 38, Nov 2021.
Subham Pokhriyal, Shweta Jain, Ganesh Ghalme, and Vaneet Aggarwal, "Anytime Fairness Guarantees in Stochastic Combinatorial MABs: A Novel Learning Framework," in Proc. AAMAS, May 2025.
Amrit Singh Bedi, Dheeraj Peddireddy, Vaneet Aggarwal, Brian M. Sadler, and Alec Koppel, "Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding," IEEE Transactions on Artificial Intelligence, vol. 6, no. 3, pp. 508-517, March 2025.
Fares Fourati, Mohamed-Slim Alouini, and Vaneet Aggarwal, "Federated Combinatorial Optimization with Multi-Agent Multi-Armed Bandits," in Proc. ICML, Jul 2024.
Fares Fourati, Christopher John Quinn, Mohamed-Slim Alouini, and Vaneet Aggarwal, "Combinatorial Stochastic-Greedy Bandit," in Proc. AAAI, Feb 2024.
Mudit Sharma, Shweta Jain, Vaneet Aggarwal, and Ganesh Ghalme, "Lipschitz Dueling Bandits over Continuous Action Spaces," in Proc. NeurIPS, Dec 2026.
Vaneet Aggarwal, Shweta Jain, Subham Pokhriyal, and Christopher John Quinn, "A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback," Transactions on Machine Learning Research, May 2026.
Keywords: combinatorial bandits, dueling bandits, Fairness, federated learning, Gaussian process bandits, multi-agent bandits, multi-armed bandits, resilience

