Matroid Bandits: Fast Combinatorial Optimization with Learning

Branislav Kveton Technicolor Labs, Zheng Wen, Azin Ashkan, Hoda Eydgahi, Brian Eriksson
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:76-85, 2014.

Abstract

A matroid is a notion of independence in combi- natorial optimization which is closely related to computational efficiency. In particular, it is well known that the maximum of a constrained mod- ular function can be found greedily if and only if the constraints are associated with a matroid. In this paper, we bring together the ideas of bandits and matroids, and propose a new class of combi- natorial bandits, matroid bandits. The objective in these problems is to learn how to maximize a modular function on a matroid. This function is stochastic and initially unknown. We propose a practical algorithm for solving our problem, Op- timistic Matroid Maximization (OMM); and prove two upper bounds, gap-dependent and gap-free, on its regret. Both bounds are sublinear in time and at most linear in all other quantities of inter- est. The gap-dependent upper bound is tight and we prove a matching lower bound on a partition matroid bandit. Finally, we evaluate our method on three real-world problems and show that it is practical.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-labs14a, title = {Matroid Bandits: Fast Combinatorial Optimization with Learning}, author = {Labs, Branislav Kveton Technicolor and Wen, Zheng and Ashkan, Azin and Eydgahi, Hoda and Eriksson, Brian}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {76--85}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/labs14a/labs14a.pdf}, url = {https://proceedings.mlr.press/r12/labs14a.html}, abstract = {A matroid is a notion of independence in combi- natorial optimization which is closely related to computational efficiency. In particular, it is well known that the maximum of a constrained mod- ular function can be found greedily if and only if the constraints are associated with a matroid. In this paper, we bring together the ideas of bandits and matroids, and propose a new class of combi- natorial bandits, matroid bandits. The objective in these problems is to learn how to maximize a modular function on a matroid. This function is stochastic and initially unknown. We propose a practical algorithm for solving our problem, Op- timistic Matroid Maximization (OMM); and prove two upper bounds, gap-dependent and gap-free, on its regret. Both bounds are sublinear in time and at most linear in all other quantities of inter- est. The gap-dependent upper bound is tight and we prove a matching lower bound on a partition matroid bandit. Finally, we evaluate our method on three real-world problems and show that it is practical.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Matroid Bandits: Fast Combinatorial Optimization with Learning %A Branislav Kveton Technicolor Labs %A Zheng Wen %A Azin Ashkan %A Hoda Eydgahi %A Brian Eriksson %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-labs14a %I PMLR %P 76--85 %U https://proceedings.mlr.press/r12/labs14a.html %V R12 %X A matroid is a notion of independence in combi- natorial optimization which is closely related to computational efficiency. In particular, it is well known that the maximum of a constrained mod- ular function can be found greedily if and only if the constraints are associated with a matroid. In this paper, we bring together the ideas of bandits and matroids, and propose a new class of combi- natorial bandits, matroid bandits. The objective in these problems is to learn how to maximize a modular function on a matroid. This function is stochastic and initially unknown. We propose a practical algorithm for solving our problem, Op- timistic Matroid Maximization (OMM); and prove two upper bounds, gap-dependent and gap-free, on its regret. Both bounds are sublinear in time and at most linear in all other quantities of inter- est. The gap-dependent upper bound is tight and we prove a matching lower bound on a partition matroid bandit. Finally, we evaluate our method on three real-world problems and show that it is practical. %Z Reissued by PMLR on 04 October 2026.
APA
Labs, B.K.T., Wen, Z., Ashkan, A., Eydgahi, H. & Eriksson, B.. (2014). Matroid Bandits: Fast Combinatorial Optimization with Learning. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:76-85 Available from https://proceedings.mlr.press/r12/labs14a.html. Reissued by PMLR on 04 October 2026.

Related Material