Matroid Bandits: Practical Large-Scale Combinatorial Bandits

Branislav Kveton, Zheng Wen, Azin Ashkan, Hoda EydgahiNational 2014

Abstract

A matroid is a notion of independence that is closely related to computational efficiency in combinatorial optimization. In this work, we bring together the ideas of matroids and multi-armed bandits, and propose a new class of stochastic combinatorial bandits, matroid bandits. A key characteristic of this class is that matroid bandits can be solved both computationally and sample efficiently. We propose a practical algorithm for our problem and bound its regret. The regret scales favorably with all quantities of interest. We evaluate our approach on the problem of learning routing networks for Internet service providers. Our results clearly show that the approach is practical.
BibTeX
@inproceedings{kveton2014matroid,
  author = {Branislav Kveton and Zheng Wen and Azin Ashkan and Hoda Eydgahi},
  title = {{Matroid Bandits: Practical Large-Scale Combinatorial Bandits}},
  booktitle = {National},
  year = {2014},
}

Loading related content...

Figure