Matroid Bandits: Fast Combinatorial Optimization with Learning

Abstract

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.

Cited by in corpus (31)

• Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
• Combinatorial Bandits Revisited
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• Cascading Bandits: Learning to Rank in the Cascade Model
• Cascading Bandits for Large-Scale Recommendation Problems
• Combinatorial Multi-Armed Bandit with General Reward Functions
• Combinatorial Cascading Bandits
• DCM Bandits: Learning to Rank with Multiple Clicks
• Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback
• Efficient Learning in Large-Scale Combinatorial Semi-Bandits
• Thompson Sampling for Combinatorial Semi-Bandits
• Deep Reinforcement Learning with Attention for Slate Markov Decision Processes with High-Dimensional States and Actions
• Online Influence Maximization under Linear Threshold Model
• Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
• Analysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms
• Combinatorial Sleeping Bandits with Fairness Constraints
• Learning to Act Greedily: Polymatroid Semi-Bandits
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
• Contextual Blocking Bandits
• Parametric Matroid Interdiction
• Combinatorial Multi-Objective Multi-Armed Bandit Problem
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
• Episodic Multi-armed Bandits
• Bandits with Knapsacks beyond the Worst-Case
• Conservative Exploration using Interleaving
• Recurrent Submodular Welfare and Matroid Blocking Bandits
• Exploiting Structure of Uncertainty for Efficient Matroid Semi-Bandits
• Combinatorial Pure Exploration with Continuous and Separable Reward Functions and Its Applications (Extended Version)
• Thompson Sampling Algorithms for Cascading Bandits
• Combinatorial Bandits for Incentivizing Agents with Dynamic Preferences
• Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem