Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy

How can a learner maximize an unknown, adversarial monotone submodular function subject to a general matroid constraint when feedback is restricted to the value of a single feasible set per round? Previous approaches either required relaxed feedback (allowing infeasible queries) or were limited to specific matroid structures like partition matroids.

The authors adapt the Poisson-process method for offline submodular maximization to the online setting. They frame the problem as learning a state-dependent exchange policy for a Poisson base walk. To overcome the exponential complexity of learning such policies, they introduce "balanced fractional exchanges," which compress the policy mixture into a single fractional base. This allows the learner to maintain a single point in the matroid base polytope and update it using entropic mirror descent, effectively reducing the submodular bandit problem to a specialized linear bandit problem.

The proposed algorithm achieves an expected (1-1/e)-regret of O(n^1/3 k^2/3 T^2/3) in the strict feasible-query model. This result disproves the conjecture that sublinear regret might be impossible for general matroids under this feedback constraint. The algorithm is computationally efficient, relying on oracle-polynomial time operations, and provides the first general solution for this class of problems.

This paper bridges a significant gap in combinatorial bandit optimization. By providing a general-purpose algorithm for matroid-constrained submodular maximization, it enables the application of submodular optimization to complex online decision-making scenarios—such as sensor placement or recommendation systems—where the objective function is unknown, adversarial, and subject to structural constraints.

Key Terms

Monotone Submodular Function

A set function exhibiting diminishing returns where adding an element to a smaller set provides at least as much value as adding it to a larger set.

Matroid Constraint

A structural constraint on a collection of items that defines which subsets are "independent" or "feasible," generalizing concepts like cardinality and partition budgets.

Poisson Base Walk

A continuous-time process that evolves a feasible base by performing single-element exchanges, used here to approximate the optimal set.

Balanced Fractional Exchange

A technique that represents a distribution over feasible exchanges as a single fractional base, allowing for efficient policy updates without tracking exponentially many individual policies.

Strict Feasible-Query Model

A bandit feedback protocol where every set queried by the algorithm must satisfy the matroid independence constraint.

AI-generated third-party summary by ResearchPod. Not official content or an endorsement by the paper authors or affiliated organizations.