- 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 -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
-
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 and , which should be stated consistently.
-
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.
-
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
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 in the -regret bound: , compared with 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.
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 T and polynomial in the number of elements n and the matroid rank k. Treating each feasible base as a separate arm gives a bound that is sublinear in T for fixed n and k. 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 T with polynomial dependence on n and k. 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 n and k is itself a substantive contribution, alongside the polynomial-time implementation.
2. Practical efficiency.
Each round our algorithm simulates at most L=O(klogT) exchanges. Constructing the exchange graphs requires O(nkL) independence-oracle calls, and their transportation flows can be computed using O(n3kL) arithmetic operations.
For the entropy projection onto Kδ, an approximate solution with Frank-Wolfe gap at most ξ can be obtained in O(1+nk/(δξ)) iterations. Each iteration solves a minimum-weight base problem by the greedy algorithm, requiring at most n independence-oracle calls and O(nlog(en)) additional operations. Thus, one approximate projection requires O(n+δξn2k) independence oracle calls and O((n+δξn2k)log(en)) additional operations. Here, δ is the shrinkage parameter and ξ 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 add at most η1∑t=1Tξt to the final expected regret bound. Choosing ξt≤ηγ makes this additional term at most γ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.