acceptodds
Under review as a conference paper at ICLR 2027

Finite Structural Queries for Asymptotically Optimal Matroid Semi-Bandits

Abstract

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 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 expected query complexity at balanced rank.

Primary area:
learning theory
Keywords:
Matroid Bandits, Combinatorial Bandits, Semi-Bandits

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_xuwdOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper considers the stochastic matroid semi-bandit problem with Bernoulli rewards where multiple arms must be selected in each round and the selected arms must form a basis of an unknown matroid. The learner has independence oracle access to the matroid and receives individual samples at each arm-pull. There are dd arms and the matroid rank is rr. The paper proposes a general algorithm that uses expected total of O(d2log⁡(r+1))O(d^2 \log(r+1)) (thus finite and polynomial) independence queries over the infinite horizon, uses memory of O(d)O(d) words, and achieves the logarithmic regret O(log⁡T)O(\log T), with the optimal coefficient (where the matroid is known). On the other hand, the number of independence queries in previous algorithms may grow with the time horizon. The authors then consider a special case in which the mean rewards are distinct and improve the number of independence queries to O(dlog⁡(r+1))O(d \log(r+1)) under the same asymptotic regret. They also provide a worst-case lower bound of Ω((d−r)log⁡r)\Omega((d-r) \log r) which matches the distinct-means algorithm when the rank is balanced (when r=Θ(d)r = \Theta(d) and d−r=Θ(d)d - r = \Theta(d)).

Critical strengths
  1. The problem is interesting and precisely formulated.
  2. The results are substantive, specially the lower bound shows that the polynomial bound only a factor of dd away from being optimal in the general case.
Critical weaknesses
  1. The writing of the paper is rough specially in the introduction. I could not understand the introduction without first reading the rest of the paper.
Questions for authors

None

3 comments

Thank you for the positive evaluation and for the comment on the introduction. We agree: we used several terms (C⋆(μ)C^\star(\mu), "certificate", "exchange partner") before defining them, and the most intuitive example appeared only in Section 5. We made three changes (in blue):

  • C⋆(μ)C^\star(\mu) is now described in words at first use (the optimal logarithmic regret coefficient of a learner that knows the matroid), with a pointer to Section 2.
  • Certificate is now defined in one sentence (the stored basis and exchange partners, together with the mean comparisons they assert).
  • The two-anchor example moved from Section 5 to the introduction, so the reader sees early why knowing the optimal basis is not enough.

For the story behind the problem (why we count structural queries separately from reward samples), please see the general response and also our response to reviewer bMY6 for a clear motivation.

Thank you also for noting that the lower bound leaves only a factor of dd in the general case. We agree that this gap under ties is the main open question, and closing it is a natural next step.

We hope our response has clearly addressed your concerns, and we are happy to address any additional questions.

I thank the authors for their response. I will keep the same positive score.

Thank you for letting us know so soon. We appreciate it.

Reviewer_tawzOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies stochastic matroid semi-bandits, where we have access to an independence oracle of the matroid. The authors propose ECR-KL, which combines a basis-exchange partner structure, KL-UCB, and statistical certificate testing and repair to achieve the known-matroid asymptotically optimal regret coefficient with O(d2log⁡(r+1))O(d^2\log(r+1)) expected total oracle queries over an infinite horizon. The paper also establishes an Ω((d−r)log⁡r)\Omega((d-r)\log r) structural query lower bound, which is matched by a Full-Order variant at balanced rank under distinct means. Experiments show that ECR-KL variants substantially reduce oracle queries compared with KL-greedy baselines, generally at the cost of higher finite-horizon regret.

Critical strengths
  1. The paper shows that the known-matroid asymptotically optimal regret can be achieved with only finitely many expected independence-oracle queries over an infinite horizon. I believe this is a significant theoretical advance over prior oracle-based approaches that require structural access growing with the time horizon. It demonstrates that structural query complexity can be bounded independently of the horizon without sacrificing regret optimality.

  2. The lower bound shows that identifying an optimal basis alone is insufficient for optimal exploration: even with identical arm means and the same optimal basis, different matroid structures can require different optimal sampling rates. This provides a fundamental justification for learning additional structural information beyond the optimal basis. Also, the full-order variant matches the query lower bound at balanced rank under distinct means, strengthening the theoretical completeness of the work.

Critical weaknesses
  1. Potentially large costs. Although ECR-KL achieves finite expected oracle queries and an asymptotically optimal regret, its repair procedure can require substantial additional reward rounds, especially when mean gaps are small. As reported by the authors, a single uniform repair requires approximately 1.77 million rounds for d=8d=8, r=4r=4, and g=0.1g=0.1. Moreover, in the larger-instance stress tests in Appendix H.3, all 25 triggered repairs remain unfinished at T=106T=10^6, and the bootstrap variant incurs substantially higher regret than the baselines. While this does not invalidate the theoretical guarantees, it raises concerns about their practical significance.

  2. Gap between theoretical guarantees and empirical results. The main experiments primarily evaluate practical variants incorporating initialization procedures, structural recognition, and direct rebuilds, and none of the main-comparison runs enters the ordinary repair procedure. Although Appendix H.3 provides small-scale diagnostics of the unmodified algorithm, these do not establish how effectively the proposed repair mechanism scales to larger instances. Consequently, the experiments demonstrate substantial oracle-query savings for practical variants, but provide limited evidence of the finite-horizon effectiveness of the core theoretically analyzed algorithm.

Questions for authors
  1. Regarding Weakness 1, could the authors provide more quantitative evidence on repair durations and stabilization times, particularly their dependence on mean gaps?

  2. Regarding Weakness 2, could the authors provide additional experimental evidence of successful certificate repair and stabilization on larger instances?

  3. The repair procedure collects fresh samples to construct confidence intervals, potentially introducing substantial additional sampling costs. Is this requirement primarily a technical choice to simplify the analysis, or is there a fundamental obstacle to reusing previously collected observations? For example, could time-uniform confidence sequences support certificate repair using existing observations while preserving the finite expected oracle-query guarantee?

3 comments

Thank you for the detailed review. We agree with both weaknesses, and we ran a new experiment on the core repair to answer Q1 and Q2.

New study (Appendix H.3, Table 19). We plant exactly one violated certificate inequality, with mean gap Δ∈0.2,0.1,0.05\Delta \in \\{0.2, 0.1, 0.05\\}, in capacity-one partition matroids with d∈4,8,16d \in \\{4, 8, 16\\} and r=d/2r = d/2. We run the core algorithm from a cold start with its original uniform repair (Algorithm 1), and the packed-sampling variant of Appendix G.1, with eight seeds per setting (144 runs, about 3.8×1093.8 \times 10^9 reward rounds). A run stops once a repair has completed and no build has occurred in the previous 10610^6 rounds, a rule fixed before any run.

Q1. Repair durations and gaps. All 144 runs trigger on the planted edge, and the trigger scale gg (half the empirical gap) is close to Δ/2\Delta/2. The trigger time scales as Δ−2\Delta^{-2} and barely depends on dd (for d=8d = 8 and uniform repair, the median is 27,722 rounds at Δ=0.2\Delta = 0.2 and 565,376 at Δ=0.05\Delta = 0.05). A uniform repair then takes exactly v mrepv\,m_{\text{rep}} rounds with mrep=⌈8d2g−2log⁡(16d2)⌉m_{\text{rep}} = \lceil 8d^2 g^{-2}\log(16d^2)\rceil (Eq. 6), which is of order d3g−2log⁡dd^3 g^{-2}\log d at balanced rank. The query count does not depend on Δ\Delta (9, 25, and 66 calls at d=4,8,16d = 4, 8, 16).

Detection is fast compared with the repair: at d=16d = 16 and Δ=0.05\Delta = 0.05, the uniform repair takes 2.46×1082.46 \times 10^8 rounds, about 430 times the trigger time. Packed sampling needs two actions per cycle here instead of d/2+1d/2+1, because every group has two arms, and at d=16d = 16 it shortens the transient by a factor of about 4.5. Gaps that do not affect the optimal basis also matter (Table 21): with the decision gap fixed at 0.15, the Full-Order ordering time grows a little over four times each time the ordering gap is halved. Section 8 now states the repair length.

Q2. Successful repair on larger instances. We extended the study to d=32d = 32, r=16r = 16 on partition, graphic, and binary linear matroids, with Δ∈0.2,0.1\Delta \in \\{0.2, 0.1\\} and four seeds per setting (48 runs, Table 20). Together with the 144 runs at d≤16d \le 16 (48 of them at d=16d = 16), every run completes one repair and has a correct certificate after two builds at the end of the observation window. At d=32d = 32, the uniform repair takes about 1.31.3 to 1.4×1081.4 \times 10^8 rounds at Δ=0.2\Delta = 0.2 and 5.35.3 to 5.4×1085.4 \times 10^8 at Δ=0.1\Delta = 0.1, nearly the same across families, since its length depends only on gg and dd. Packed repair shortens it by about 8.5, 4.3, and 1.5 to 1.7 times on partition, graphic, and binary linear instances, whose largest groups have 2, 4, and 10 or 11 arms (the graphic and binary instances differ between the two gaps, so we measure the gap dependence at d≤16d \le 16).

These runs validate the core repair beyond partition matroids, but small gaps stay out of reach: at d=32d = 32 and gap 0.02, assuming g≈Δ/2g \approx \Delta/2, Eq. 6 gives about 1.4×10101.4 \times 10^{10} rounds for one uniform repair. This is consistent with the separate stress study (bootstrap prefix with targeted repair), where 25/128 runs are still in repair at T=106T = 10^6, across nominal gaps 0.02 and 0.05, with mean regret 8.02 times that of KL-OSM (Table 15). We keep this limitation explicit in Sections 6 and 8. In contrast, on the 16 connected instances of Section 6, the refreshed parallel policy makes 558 queries against 39,224 for KL-greedy, with 3.1% higher regret. Our main claim remains theoretical: a horizon-independent expected query bound without giving up the regret coefficient C⋆C^\star.

Q3. Why fresh samples? Fresh samples are required by our current proof technique, and we do not claim that they are information-theoretically necessary. The KL indices already use every observation, including all repair samples. Only the local tests and the repair intervals use fresh samples. With fresh samples, each episode ends in a bad refinement with probability at most 1/(4d)1/(4d), conditional on the whole history at its build (Lemmas D.1 and D.2), which gives EK≤4dL/(d+L+1)\mathbb{E}K \le 4dL/(d+L+1) and an exponential tail for KK (Lemma D.3). If repairs reused old data, errors at different builds would be dependent. Time-uniform confidence sequences (Howard et al., 2021), with error budgets that shrink across builds, may remove this requirement. The global test of Proposition 4 is a partial step: it reuses all observations and keeps the expected query count finite, but it can trigger only a bounded number of direct rebuilds. We added this discussion after Lemma D.2.

References

  • Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055–1080, 2021.

We hope our response has clearly addressed your concerns, and we are happy to address any additional questions.

Thank you for the response. I will maintain my score.

Thank you for reading our response and for maintaining your score. We appreciate it.

Reviewer_bMY6OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the following bandit problem.

There are a set of arms {ai}\{a_i\}, and a matroid over these arms. At any time, the learner must select a feasible set At={aik}A_t = \{a_{i_k}\} for some set I={i1,i2,⋯ ,iN}I=\{i_1, i_2, \cdots, i_N\} and observes the individual rewards corresponding to the selected arms. The objective is to minimize regret.

To satisfy the constraint that the learner must select a maximal feasible set at all times (a basis), the learner is also given access to an oracle that it can use to query whether any specific subset of arms is feasible.

The paper shows how to achieve asymptotic regret that is the same as if the learner knew the matroid that constraints the feasible sets with only a polynomial number of oracle queries.

Critical strengths

This is an interesting problem. The algorithm is novel and non-trivial. I think the key idea is that the entire matroid is never checked for feasibility, rather the algorithm only identifies a single basis, and then finds one partner for every arm outside this basis that can be exchanged to remain feasible. This allows the learner to get away with polynomially many queries for feasibility.

Critical weaknesses

A trivial search over all feasible sets allows the learner to know all feasible sets within exponentially many (but finite) number of queries. The paper only claims that one can get away with a polynomial number of queries in expectation and still get asymptotically the same regret as a learner who knows the matroid. In this sense, knowing the matroid exactly vs doing a brute force to learn the matroid are two settings that sandwich this one.

There also doesnt seem to be any motivation for studying this problem, though matroid bandits are studied.

Questions for authors

Can this problem be motivated from first principles?

3 comments

Thank you for the positive assessment, and for summarizing the key idea (one basis plus one exchange partner per outside arm) so precisely.

First, the motivation from first principles. We want to answer this question directly, with three reasons.

(i) A general matroid cannot be stored explicitly. The number mnm_n of matroids on nn elements satisfies log⁡2log⁡2mn≥n−32log⁡2n−O(1)\log_2\log_2 m_n \ge n - \tfrac{3}{2}\log_2 n - O(1) (Knuth, 1974). A simple version of this counting argument shows that any representation covering all matroids on 64 elements must use more than 101610^{16} bits for some of them (a uniform matroid, by contrast, needs only dd and rr). The construction deletes, from a uniform matroid, a family of rr-sets that pairwise share at most r−2r-2 elements, and Appendix E.3 uses the same idea with a single deleted set. So the independence oracle is the natural access model, and query complexity is the natural cost measure, as in matroid algorithms (for example, Karp et al., 1988). ECR-KL itself stores only O(d)O(d) words.

(ii) Some oracles are expensive. For a linear matroid, each query is a rank computation. For a transversal matroid (can these jobs be assigned to distinct machines?), it is a bipartite matching. For a gammoid (can these flows be routed on vertex-disjoint paths?), it is a max-flow computation. Banihashem et al. (2026) make a related point: even for graphic matroids a single query can take time linear in the size of the queried set, and they study a cost model in which a query on QQ costs ∣Q∣|Q|. For uniform or partition matroids, queries are cheap, so our results matter most when the constraint is given implicitly.

(iii) A query cost changes the comparison. Suppose each query costs c>0c > 0 in the same units as regret, and let JT=Rμ(T)+c E[QT]J_T = R_\mu(T) + c\,\mathbb{E}[Q_T]. Theorem 1 gives JT≤C⋆(μ)f(T)+Aμ(f(T)+1)+c 4dLd+L+1 cd,rJ_T \le C^\star(\mu) f(T) + A_\mu(\sqrt{f(T)}+1) + c\,\tfrac{4dL}{d+L+1}\,c_{d,r}, where the query term does not depend on TT. An uncached greedy scan, as in KL-OSM, makes at least rr calls per round, so its query term grows linearly in TT. MAUB uses Oμ(log⁡log⁡T)O_\mu(\log\log T) update rounds, so its query term is o(log⁡T)o(\log T). Against MAUB, the gain is a total structural cost that stays bounded for every horizon, together with the exact coefficient C⋆C^\star (MAUB proves Oμ(log⁡T)O_\mu(\log T) regret).

Second, the "sandwich" between knowing the matroid and brute force. We agree that these are the two easy endpoints. Between them, the answer is sharp under distinct means at balanced rank, and a factor-dd gap remains with ties.

  1. Brute force is exponential. Querying all (dr)\binom{d}{r} rank-rr sets is exponential at balanced rank (r,d−r=Θ(d)r, d-r = \Theta(d)). ECR-KL makes O(d2log⁡(r+1))O(d^2 \log(r+1)) expected queries with arbitrary ties, and Full-Order ECR-KL makes O(dlog⁡(r+1))O(d \log(r+1)) under distinct means (Table 1).
  2. There is a matching lower bound. Every universally feasible, uniformly efficient policy that attains C⋆C^\star at every unique-optimum instance needs at least (d−r)log⁡2r(d-r)\log_2 r expected queries on some instance (Theorem 2). So under distinct means at balanced rank, the optimal worst-case expected query complexity is Θ(dlog⁡d)\Theta(d \log d) (Theorem 3).
  3. Identifying the matroid and then stopping is expensive. A policy that announces at a finite time that it will make no further queries must identify the entire matroid, and on a hidden uniform matroid this needs (dr)\binom{d}{r} queries (Proposition 1). ECR-KL gets a polynomial bound because it never announces its last query.

Finally, more details about "in expectation". The number of builds also has an exponential tail (Lemma D.3, Eq. 17), and each build makes at most d+(d−r)⌈log⁡2r⌉d + (d-r)\lceil \log_2 r \rceil queries. So a run with many more queries than the mean is exponentially unlikely.

We would be grateful if you could look again at Theorem 2 and Proposition 1 with this view.

References

  • Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, and Danny Mittal. Matroid algorithms under size-sensitive independence oracles. ICML, PMLR 306, pp. 6309–6324, 2026.
  • Richard M. Karp, Eli Upfal, and Avi Wigderson. The complexity of parallel search. Journal of Computer and System Sciences, 36(2):225–253, 1988.
  • Donald E. Knuth. The asymptotic number of geometries. Journal of Combinatorial Theory, Series A, 16:398–400, 1974.

We hope our response has clearly addressed your concerns, and we are happy to address any additional questions.

Thanks for the response. I will keep my positive score.

Thank you for reading our response and for maintaining your score. We appreciate it.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Our Motivation, Key Contributions and Summary of Revisions

We thank the three reviewers for their careful reading. All three recognized the contribution and raised no concern about soundness, and we are grateful for that. Reviewer bMY6 asked for the motivation, and Reviewer xuwd found the introduction hard to follow. So before the individual replies, we want to position the story behind the problem.

Where we started. In sequential decision making, online interaction can overcome the coverage limitations of a fixed dataset, because the learner collects observations where it is uncertain (Jin et al., 2021; Rashidinejad et al., 2021; Xie et al., 2023). Online queries have a price, though, and a large part of this literature tries to spend fewer of them, from fixed-confidence best-arm identification (Garivier & Kaufmann, 2016) to query-efficient RLHF with human annotators (Ji et al., 2025).

The gap we saw. In matroid semi-bandits, the learner uses two distinct resources: reward observations and access to an implicitly represented feasibility structure. Unlike a reward sample, an independence query may require an expensive operation, such as a rank computation or a bipartite matching, while a certified basis can be replayed without further queries. Prior methods (Talebi & Proutière, 2016; Delage & Gaudel, 2025; Kim et al., 2025) have oracle-access guarantees that depend on the horizon TT, although they use different oracle models (Table 1). So we explicitly ask: can a learner attain the regret coefficient C⋆(μ)C^\star(\mu) of the known-matroid problem while querying the structure only finitely many times? Theorem 1 answers yes, in expectation. Theorem 2 shows that learning an optimal basis is not enough. For each suboptimal outside arm, the exchange partner fixes the insertion threshold mim_i, and hence the optimal sampling rate 1/kl(μi,mi)1/\mathrm{kl}(\mu_i, m_i).

Summary of the revision (in blue).

  1. The introduction now defines C⋆(μ)C^\star(\mu) and "certificate" at first use, gives two costly queries (a rank computation for a linear matroid, a bipartite matching for a transversal matroid), cites Proposition 1, and contains the two-anchor example (moved from Section 5).
  2. A new planted-error study of the core repair (Appendix H.3, Tables 19 and 20), with d≤32d \le 32 and partition, graphic, and binary linear matroids.
  3. A remark on why repairs use fresh samples (Appendix D.1, after Lemma D.2).
  4. To stay within nine pages, we moved the recognition table of Section 6 to Appendix H.2, without changes.

References

  • Aurélien Delage and Romaric Gaudel. Efficient matroid bandit linear optimization leveraging unimodality. arXiv:2512.00605, 2025.
  • Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. COLT, PMLR 49, pp. 998–1027, 2016.
  • Kaixuan Ji, Jiafan He, and Quanquan Gu. Reinforcement learning from human feedback with active queries. Transactions on Machine Learning Research, 2025.
  • Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? ICML, PMLR 139, pp. 5084–5096, 2021.
  • Jung-hun Kim, Milan Vojnović, and Min-hwan Oh. Oracle-efficient combinatorial semi-bandits. NeurIPS 38, pp. 28269–28304, 2025.
  • Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. NeurIPS 34, 2021.
  • Mohammad Sadegh Talebi and Alexandre Proutière. An optimal algorithm for stochastic matroid bandit optimization. AAMAS, pp. 548–556, 2016.
  • Tengyang Xie, Dylan J. Foster, Yu Bai, Nan Jiang, and Sham M. Kakade. The role of coverage in online reinforcement learning. ICLR, 2023.
AuthorsOpenReview ↗

Closing Remarks from Authors

Dear Area Chair and Reviewers,

We thank the three reviewers for their careful reading and constructive discussion. We were glad that all reviewers found the problem interesting, recognized the theoretical contribution, and raised no concern about soundness.

The discussion focused on two points, which we addressed in the revised PDF (changes in blue):

  • Motivation and presentation (bMY6, xuwd). We explained why query complexity is the natural cost measure for matroids and how our problem lies between knowing the matroid and brute-force identification (Theorem 2, Proposition 1). The introduction now defines its key terms at first use.
  • Cost of repair (tawz). A new planted-error study (Appendix H.3, Tables 19 and 20) shows that the core repair completes with a correct certificate in all 192 runs, for dd up to 32 on three matroid families. We also state explicitly that the transient can be long (Sections 6 and 8).

After the discussion, all three reviewers confirmed their positive scores. We are grateful for their questions, which made the paper clearer. We hope this summary is helpful for the final assessment.

Best regards,

The authors of Submission 21357

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.