Matroid Bandits: Fast Combinatorial Optimization with Learning
This work addresses the challenge of efficient combinatorial optimization under uncertainty for applications in areas like resource allocation or recommendation systems, representing a novel integration of bandits and matroids rather than an incremental advance.
The paper tackles the problem of maximizing a stochastic modular function on a matroid by introducing matroid bandits, a new class of combinatorial bandits, and proposes the Optimistic Matroid Maximization (OMM) algorithm with sublinear regret bounds, including a tight gap-dependent bound and practical evaluation on real-world problems.
A matroid is a notion of independence in combinatorial optimization which is closely related to computational efficiency. In particular, it is well known that the maximum of a constrained modular 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 combinatorial 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, Optimistic 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 interest. 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.