Finite Structural Queries for Asymptotically Optimal Matroid Semi-Bandits

Stochastic matroid semi-bandit algorithms typically assume continued access to an independence oracle. We show that asymptotically optimal regret is achievable with only finitely many oracle queries in expectation over an infinite horizon. For Bernoulli rewards, we introduce ECR-KL, which stores a basis and one feasible exchange partner for each outside element. The partners define groups for simultaneous exploration. Fresh samples are used to test and repair the mean comparisons. It handles arbitrary ties, uses $O(d)$ words of memory, and has a polynomial expected query bound that does not depend on the horizon. ECR-KL attains the optimal logarithmic regret coefficient of the known-matroid problem, including at nonunique optima. A structural lower bound shows that hidden matroids with the same mean vector and optimal basis can require different optimal sampling rates. When all means are distinct, a full-order variant matches the optimal $\Theta (d\log d)$ expected query complexity at balanced rank.