Efficient Matroid Bandit Linear Optimization Leveraging Unimodality

Aurélien Delage, Romaric Gaudel

We study the combinatorial semi-bandit problem under matroid constraints. The regret achieved by recent approaches is optimal, in the sense that it matches the lower bound. Yet, ti…