Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Matroid Bandits: Fast Combinatorial Optimization with Learning
Branislav Kveton, Zheng Wen, Azin Ashkan, Hoda Eydgahi, Brian Eriksson
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.
Pages: 420-429
PS Link:
PDF Link: /papers/14/p420-kveton.pdf
AUTHOR = "Branislav Kveton and Zheng Wen and Azin Ashkan and Hoda Eydgahi and Brian Eriksson",
TITLE = "Matroid Bandits: Fast Combinatorial Optimization with Learning",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "420--429"

hosted by DSL   •   site info   •   help