acceptodds
Under review as a conference paper at ICLR 2027

Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy

Abstract

We study adversarial bandit maximization of monotone submodular functions under a matroid constraint. For a rank- matroid on elements, we give a randomized oracle-polynomial algorithm that makes one feasible value query per round and has expected -regret . This is the first sublinear-regret algorithm for adversarial bandit submodular maximization under general matroid constraints. Technically, we view the problem as learning an exchange policy for the Poisson base walk. This connects the problem to contextual bandits and gives an information-theoretic sublinear-regret guarantee, but directly learning the exponentially many policies requires exponential time and space. We therefore introduce balanced fractional exchanges, which compress the policy mixture into a single fractional base while retaining the exchange information needed by the Poisson analysis. This leads to an polynomial time algorithm with the same regret guarantee.

Primary area:
learning theory
Keywords:
Bandit, Submodular maximization

Reviews

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

The paper studies adversarial monotone submodular maximization under a general matroid with one feasible value query per round. Building on a recent offline Poisson-walk algorithm, it introduces a fractional exchange representation and a feasible bandit estimator, obtaining an oracle-polynomial algorithm with expected (1−1/e)(1-1/e)-regret $\widetilde O(n^{1/3}k^{2/3}T^{2/3}) $.

The contribution of the paper is mostly theoretical. I am a bit concerned about the practicality of the framework and the algorithm. It would be helpful to provide more concrete practical examples and experiments that demonstrate the algorithm's practical value.

Critical strengths
  • The paper addresses a meaningful gap between partition-matroid bandit results and general-matroid methods that allow infeasible exploratory queries.

  • The reduction from state-dependent exchanges to linear regret over the base polytope is useful. Together with the one-query estimator, it gives a substantive extension of the offline Poisson framework.

Critical weaknesses
  1. The novelty claim should be qualified. Sublinear regret alone is obtainable by treating every base as an arm, at exponential cost. The contribution is polynomial-time learning with controlled dependence on nn and kk, which should be stated consistently.

  2. Practical efficiency remains unclear. Each round requires multiple transportation-flow computations and an entropy projection. The paper provides no implementation or empirical evidence, and the guarantee becomes informative only for sufficiently large horizons.

  3. The application discussion is high level. The examples do not specify a concrete non-partition matroid or explain how the reward and feedback assumptions are satisfied. Exploration also plays smaller independent sets, which may be unsuitable when complete configurations are mandatory.

Questions for authors
  • Can the authors provide a worked example beyond partition matroids, including the feasibility of exploratory subsets?

  • Can the authors provide explicit bounds on the number of independence-oracle calls and total running time per round, including the transportation-flow computations and entropy projection? If the projection is computed approximately, how accurately must it be solved to maintain feasibility and preserve the stated regret bound, and how does this accuracy requirement affect the running time?

3 comments

Thank you for your positive evaluation!

1. Contribution positioning.

In the combinatorial bandit setting, the relevant goal is a regret bound that is sublinear in TT and polynomial in the number of elements nn and the matroid rank kk. Treating each feasible base as a separate arm gives a bound that is sublinear in TT for fixed nn and kk. The dimension dependence of that bound, however, scales with the square root of the number of bases, up to logarithmic factors. Even a uniform matroid can have exponentially many bases. The resulting regret bound therefore has exponential dependence on the problem dimensions, regardless of the computational cost.

Our first construction in Section~1.1 achieves sublinear regret in TT with polynomial dependence on nn and kk. It learns over an exponentially large class of exchange policies, but the regret depends only logarithmically on the number of policies. Obtaining this regret guarantee is itself nontrivial and constitutes our first main contribution. We then develop a method that achieves the same regret guarantee in polynomial time, which constitutes our second main contribution. Thus, the sublinear regret guarantee with polynomial dependence on nn and kk is itself a substantive contribution, alongside the polynomial-time implementation.

2. Practical efficiency.

Each round our algorithm simulates at most L=O(klog⁡T)L=O(k\log T) exchanges. Constructing the exchange graphs requires O(nkL)O(nkL) independence-oracle calls, and their transportation flows can be computed using O(n3kL)O(n^3kL) arithmetic operations.

For the entropy projection onto KδK_\delta, an approximate solution with Frank-Wolfe gap at most ξ\xi can be obtained in O(1+nk/(δξ))O(1+nk/(\delta\xi)) iterations. Each iteration solves a minimum-weight base problem by the greedy algorithm, requiring at most nn independence-oracle calls and O(nlog⁡(en))O(n\log(en)) additional operations. Thus, one approximate projection requires O(n+n2kδξ)O\left(n+\frac{n^2k}{\delta\xi}\right) independence oracle calls and O((n+n2kδξ)log⁡(en))O\left(\left(n+\frac{n^2k}{\delta\xi}\right)\log(en)\right) additional operations. Here, δ\delta is the shrinkage parameter and ξ\xi is the projection tolerance. These are worst-case bounds obtained from the standard Frank-Wolfe convergence guarantee.

Projection errors accumulate linearly in the regret analysis. Specifically, feasible approximate projections with Frank--Wolfe gaps at most ξt\xi_t add at most 1η∑t=1Tξt\frac{1}{\eta}\sum_{t=1}^{T}\xi_t to the final expected regret bound. Choosing ξt≤ηγ\xi_t\le\eta\gamma makes this additional term at most γT\gamma T, preserving our stated regret order.

We use exact projections in the main analysis to keep the presentation concise. Tracking these approximation tolerances throughout the proof would make the exposition unnecessarily complicated.

3. Applications

Matroid constraints are widely used in combinatorial optimization and capture a broad range of practical feasibility requirements. Previous work on adversarial bandit submodular maximization under standard bandit feedback has largely focused on special cases such as partition matroids. General matroids also include graphic and laminar matroids, which capture other practical constraints.

A graphic matroid has graph edges as elements and forests as independent sets. It models active-link selection in monitoring networks that require loop-free forwarding. Each active link monitors its own traffic, so partial forests are also feasible for exploration. A laminar matroid captures nested capacity constraints. For example, each of two buildings may support at most two active sensor streams, while their shared gateway supports at most three streams in total.

In both examples, bandit feedback arises when the learner observes only an aggregate score after deployment, such as the normalized number of distinct incidents detected. Counting each incident once gives a monotone submodular coverage reward. Feasible exploration in these examples is essential. In the network example, the controller rejects cyclic configurations because they can cause forwarding loops and congestion. In the sensor example, exceeding either capacity limit requires unavailable channels, so the configuration cannot be deployed. Since observing the reward requires operating the selected configuration, these constraints apply equally to exploration and exploitation.

At the last, even setting aside our contribution to feasible exploration, our algorithm achieves a better dependence on TT in the (1−1/e)(1-1/e)-regret bound: O~(T2/3)\widetilde O(T^{2/3}), compared with O(T8/9)O(T^{8/9}) achieved by Zhang et al. (2019) under the relaxed responsive bandit model.

I thank the authors for their response. It helped clarify my questions and concerns. I have no further comments and will keep my score.

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

In this paper, they consider the problem of Online Submodular Maximization under bandit feedback and general matroid constraints. An oblivious adversary fixes a sequence of monotone and submodular functions f1,…,fTf_1, \dots, f_T. At time tt, the learner selects an independent set StS_t and receives only the feedback ft(St)f_t(S_t). The goal is to achieve sublinear (1−1/e)(1-1/e)-regret.

The main contribution is the first algorithm with sublinear regret for bandit-feedback Online Submodular Maximization under general matroid constraints and polynomial dependence on the problem dimensions. The main idea is to extend the recent algorithm of Ganz Rozenman et al. (2026) from the offline to the online setting. The algorithm runs a Poisson base walk at every tilmestep tt. In order to implement the algorithm online, they connect the problem to contextual bandits and introduce the notion of balanced fractional exchanges, allowing a learned fractional base xtx_t to guide the walk. . Finally, the online algorithm needs to carefully balance exploitation, where they play the final base of the Poisson walk, with exploration, where they use a feasible query to estimate a linear loss and update xtx_t.

Critical strengths
  • They solve an important open problem in the field, i.e., bandit feedback Online Submodular Maximization under general matroid constraints.
  • The proposed algorithm naturally builds upon the recent idea of a Poisson base walk introduced for maximizing submodular functions in the offline setting.
  • I did not identify any issue in the proofs.
Critical weaknesses
  • The importance of the flow method for implementing the balanced fractional exchanges seems a bit overstated. As discussed in Appendix C, one can use a decomposition of the fractional point into matroid bases. Such a decomposition can be computed efficiently for matroids. It would be helpful to discuss the benefits of each approach.
  • No experiments and comparison with prior benchmarks (at least for cardinality or partition matroid). Such experiments might reveal practical inefficiencies that will in turn lead to useful theory and new research questions.
  • The presentation can be improved. Specifically, I found it a bit hard to follow the technical overview. The roles of the fractional point xtx_t, the internal Poisson walk, and the single bandit observation are hard to connect. A short description of one complete online round emphasizing that the Poisson walk is simulated inside each round tt would be helpful. Sections 4–5 could benefit from an informal explanation of the algorithm before introducing the detailed constructions and proofs.
Questions for authors
  • (Balanced fractional exchanges) What are the computational or practical advantages of the flow construction over the decomposition-based implementation described in Appendix C?
  • (Experiments) I would like to ask the authors to run a few experiments. For example, they can generate a few synthetic datasets or use some datasets from prior work. Then, test their algorithm under various constraints and compare it with prior algorithms (at least for cardinality constraints). Even if the results reveal practical limitations, I think the paper would be much stronger and the community will greatly benefit.
  • Do you think the regret bound of order T2/3T^{2/3} is a limitation of the proposed approach or a fundamental barrier? Do you see a route towards a better dependence on TT?
3 comments

Thank you for recognizing our work!

1. About balanced fractional exchanges (Question 1)

We agree that the decomposition-based implementation is a valid alternative. The main advantage of our construction is that it works directly with the fractional vector xtx_t, without requiring an explicit convex decomposition into matroid bases.

The decomposition-based implementation first computes a representation $ x_t=\sum_r\lambda_r\mathbf 1_{B_r}$, and then samples a base and uses a Brualdi bijection to generate feasible exchanges. However, the base decomposition itself is costly. Cunningham’s classical algorithm [1] obtains such a decomposition using O(n6)O(n^6) independence-oracle calls. As xtx_t evolves online, an explicit decomposition must be obtained or maintained for the updated fractional vectors.

Our flow construction avoids this preprocessing. Given the current base AA and the coordinates of xtx_t, it constructs a transportation network with n+k+2n+k+2 vertices and O(nk)O(nk) arcs. Identifying the feasible exchange arcs requires O(nk)O(nk) independence-oracle calls. The remaining computation is an ordinary flow problem requiring no further matroid-oracle calls; a standard O(V2E)O(V^2E) max-flow algorithm gives an O(n3k)O(n^3k) arithmetic-operation bound. Thus, for at most LL Poisson events per round, exchange construction uses O(nkL)O(nkL) independence-oracle calls and O(n3kL)O(n^3kL) arithmetic operations.

The benefit is therefore a direct, decomposition-free implementation that naturally accommodates an online optimizer supplying xtx_t in coordinate form. When a decomposition is already available, the decomposition-based approach remains a useful alternative.

[1] W. H. Cunningham. Testing membership in matroid polyhedra. Journal of Combinatorial Theory, Series B, 36(2):161–188, 1984.

2. About the regret bound (Question 3)

Thank you for this thoughtful question. So far we do not know whether the T2/3T^{2/3} dependence is optimal. A relevant result is by Tajdini et. al. [2], which establishes lower bounds exhibiting a T2/3T^{2/3} dependence in certain parameter regimes. However, their lower bounds concern a different performance measure, called robust greedy regret, in the stochastic cardinality-constrained setting. This quantity upper-bounds the standard (1−1/e)(1-1/e)-regret. Consequently, a lower bound on RgrR_{\mathrm{gr}} does not automatically imply the same lower bound on R1−1/eR_{1-1/e}. Their result suggests a barrier for the stronger robust greedy benchmark, but does not by itself establish a corresponding barrier for the standard approximation regret considered here.

Overall, our primary goal is to establish that sublinear (1−1/e)(1-1/e)-regret is achievable under general matroid constraints with polynomial dependence on the problem dimensions. Since bandit submodular maximization is typically studied through scaled regret, even a small improvement in the approximation factor can outweigh an improvement in the additive regret term. We regard achieving this approximation factor together with sublinear regret as the central contribution. Improving the additive regret while retaining these properties would certainly be interesting, but we have not attempted to optimize its dependence on TT in this work.

[2] A. Tajdini, L. Jain, and K. Jamieson. “Nearly Minimax Optimal Submodular Maximization with Bandit Feedback.” Advances in Neural Information Processing Systems, 37:96254–96281, 2024.

3. Experiments (Question 2)

We conducted experiments under both cardinality and graphic matroid constraints. We found these experiments particularly informative, as they helped clarify the practical trade-offs within our framework. The experimental curves and detailed settings are available in our anonymous repository.

Our framework reduces the original problem to online linear optimization over a compressed exchange policy xt∈P(M)x_t\in\mathcal{P}(\mathcal{M}), and connects the regret of this inner optimizer to the final approximation-regret bound. Our theoretical implementation uses entropic mirror descent and entropy projections, which we found not so good in practice. So for the experiments, we use an FTPL subprogram to update xtx_t by averaging perturbed maximum-weight bases. The overall implementation retains the Poisson-walk framework described in the paper, with FTPL serving as the inner optimizer for xtx_t.

Both experiments use synthetic weighted coverage functions whose weight means drift smoothly between targets with different optimal subsets. Realized weights receive Gaussian perturbations on every round, including periods with fixed means. We run T=500,000T=500{,}000 rounds over 80 paired test seeds, with parameters selected on separate development seeds. Performance is measured by cumulative reward divided by the reward of the best fixed feasible set, including all exploration rounds.

Cardinality constraint. We use n=20n=20 and k=5k=5, with two smooth objective transitions, and compare our method with cardinality-specific algorithm OGo [4] and ETCG [3] (which is designed for the stochastic environment). Our method performs close to the OGo, and both substantially outperform ETCG.

Graphic matroid. We use n=30n=30 edges and rank k=6k=6, with three smooth objective transitions. We compare our method with a feasibility-aware greedy extension of ETCG and classic EXP3, which treats each of the 123,904 feasible forests as a separate arm. Our method substantially outperforms both baselines.

The following table reports the mean cumulative reward ratio at the final horizon (larger is better).

ConstraintnnkkoursOGoETCGEXP3
Cardinality2050.8350.8500.189—
Graphic matroid3060.804—0.2900.448

[3] Guanyu Nie, Mridul Agarwal, Abhishek Kumar Umrawal, Vaneet Aggarwal, and Christopher John Quinn. An explore-then-commit algorithm for submodular maximization under full-bandit feedback. Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, PMLR 180:1541–1551, 2022.

[4] Matthew Streeter and Daniel Golovin. An Online Algorithm for Maximizing Submodular Functions. Advances in Neural Information Processing Systems 21, pp. 1577–1584, 2008.

Thanks for your clarifications. I will maintain my score.

Reviewer_tWChOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

In this paper, the authors study the classical problem of submodular maximization under general matroid constraints in the adversarial bandit setting. They propose a randomized algorithm based on Poisson analysis and achieve an expected ((1-1/e))-regret bound of (O(n^{1/3}k^{2/3}T^{2/3})), using one feasible value query per round. This is the first polynomial-time algorithm to achieve sublinear ((1-1/e))-regret in this setting.

Critical strengths
  1. The paper studies a classical and challenging problem of submodular maximization under bandit feedback, extending existing results to general matroid constraints.

  2. The proposed algorithm achieves a sublinear regret bound with rigorous theoretical analysis. The paper is also generally well organized, and the analysis is clear and easy to follow.

Critical weaknesses
  1. The novelty of the technical contributions could be articulated more clearly. The analysis relies heavily on the Poisson base-walk framework of Ganz Rozenman et al. (2026), while several other components, such as entropy-based online mirror descent, are based on standard online-learning techniques. Although the balanced fractional exchange construction and feasible leave-one-out estimator appear central to overcoming the computational and feedback constraints, the paper could do more to isolate the key technical challenges and explain precisely what new insights are required beyond the existing Poisson analysis.

  2. Although the introduction provides application examples and the related-work section discusses several relevant studies, the paper could more clearly explain why the general-matroid setting is important in practice and what limitations of existing approaches make the proposed result necessary. In particular, a more explicit comparison with prior adversarial bandit methods, as well as stochastic full-bandit approaches, would help readers understand the precise gap addressed by this work.

Questions for authors

Please refer to the weaknesses section for more details. In particular, a more thorough discussion of the novelty of the technical contributions, a detailed comparison with existing work on submodular maximization under bandit feedback, and additional motivating examples explaining the importance of this problem would strengthen the paper. One potentially relevant work is Xu, Zirui, Xiaofeng Lin, and Vasileios Tzoumas, “Bandit Submodular Maximization for Multi-Robot Coordination in Unpredictable and Partially Observable Environments” (arXiv:2305.12795, 2023), which also studies submodular maximization with partition matroid constraint under adversarial bandit feedback.

3 comments

Thank you again for your feedback. We have updated the manuscript to cite and discuss Xu et al. (2023) and added a brief discussion of applications of general matroids, including graphic and laminar matroids. These changes are highlighted in blue.

We also noticed the soundness score of 1, but could not identify specific correctness concerns in the written review. If you have any concerns about the correctness of our results or proofs, we would be very happy to provide further clarification.

Thanks for the authors' reply. My concerns about the technical novelty have been addressed. However, I still find the literature review insufficiently thorough. A more detailed literature review on submodular bandit should be presented. For example, the authors also mentioned topics like contextual bandit, from offline bound to online regret etc. I recommend that the authors revise the related work section to make it more complete. In light of the rebuttal, I have raised my score.

Thank you for your response! As the author rebuttal period is drawing to a close, we are unable to submit a revision immediately. We guarantee that a much more detailed literature review will be included in the final version.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.