Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of matroid semi-bandits with an additional condition that each arm becomes unavailable for a fixed duration after it is played. The paper first considers an "offline" version of the problem where the reward for each arm is already known and the goal is to design an optimal schedule for playing the arms. A randomized greedy algorithm is proposed which is (1-1/e)-competitive to an optimal algorithm. The paper then shows that this algorithm can be extended to the `online' version of the problem when the rewards are unknown. This is because the set of arms played in this greedy schedule only depends on the delays and does not depend on the rewards. This online algorithm suffers an additional regret of O(K\sqrt{T} + K^2) in comparison to the best offline solution. 
main_review: Sub-optimality of Regret: The regret upper bound presented in the paper seems to be weak along a few dimensions. Firstly, there is a K^2 dependence in the regret bound which is large for any practical application. Is this K^2 dependence really needed for this problem or is it just an artefact of the algorithm/analysis? I would like to believe that it is the latter since \Delta_{ij} contains information about \Delta_{kj} which can perhaps be exploited. Secondly, there is a dependence on d_{\max} which can be large if a few arms are blocked for a long time. 

Technical Depth: Even though the theoretical results are sound, I did not find much technical depth in the algorithm and analysis. The analysis of (1-1/e) competitiveness in the "offline" case follows the usual multilinear extension/concave closure "correlation gap" technique from submodular optimization. In the "online" extension I liked the use of "strong basis exchange" property of matroids, however, the rest of the argument follows from an "UCB-type" analysis of the gaps/regret of the arms. 

Known delays: The assumption that the delays for each arm is known is not realistic. Is it possible to extend this algorithm to the case when delays are stochastic in nature and only the expected delay for each arm is known?

Summary of review: This paper proposes an interesting problem and proposes sound theoretical results for this problem. However, there are several issues outlined above due to which I think this paper is borderline.




limitations_and_societal_impact: The broader impact section is not provided. I do not see any immediate negative impacts.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces matroid blocking semi-bandits (MBB), which generalizes blocking bandits and matroid bandits. To solve the full-information variant of MBB, the authors reduce it to Recurrent Submodular Welfare (RSW) and propose a novel technique of interleaved scheduling to achieve a (1-1/e)-approximation. For the bandit setting of MBB where the mean arm rewards are unknown, based on the result from the full-information setting, they propose an UCB-type algorithm with regret guarantees.
main_review: 1) Originality:
One key idea of this paper is reducing the full-information MBB to RSW, which is novel and serves as the cornerstone for the bandit setting. To solve RSW, the authors develop the interleaved scheduling technique motivated by [25] to design a (1-1/e)-approximation algorithm. They also prove the (1-1/e)-approximation ratio is asymptotically tight. Based on these results, they propose a UCB-based algorithm for the bandit setting. Their regret analysis uses the strong basis exchange property of matroids to decompose regret, then follows [28] to derive the regret guarantee.

2) Quality:
This paper is technically sound. Most of the claims are supported by theoretical analysis.

3) Clarity:
This paper is clearly written and well organized.

4) Significance:
The main technical contributions of this paper are: (1) Reducing the full-information MBB to RSW; (2) (1-1/e)-approximation algorithm for RSW; (3) Using the strong basis exchange property of matroids to decompose regret for the regret analysis.

limitations_and_societal_impact: 1) Though the authors discuss the main steps of reducing MBB to RSW on line 127-150, more details on why player A's task is a special case of RSW are missing (line 298-308 only discuss the algorithm and the theorem).
2) Once the full-information setting is solved, the UCB-based algorithm for the bandit setting is somewhat standard. Though the regret analysis becomes harder and the authors use some properties of matroids, the remaining parts are based on [25].
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors consider the problem of Matroid Blocking Semi-Bandits. In this setting, there are $k$ arms, an unknown time horizon $T$ and a matroid dictating which sets of arms can be pulled at each step. Pulling each arm yields a reward, which comes from an unknown probability distribution with mean $\mu_i$. Moreover, each arm $i$ remains blocked after use for $d_i$ steps. Observing only the rewards from the used arms, the goal is to maximise the sum of all rewards collected over the time horizon $T$. 

There are 3 main results, which can be better explained by a minor detour in the full information setting (where the $\mu_i$ are known). In this setting, the first approach one would follow is to ignore the $d_i$’s and just chose the independent set maximising the current rewards, among the arms that are not blocked. However, this is not optimal (for general matroids): the catch is that the underlying matroid indirectly affects the rewards of each arm, by restricting which other arms can be used together. To get around this, the authors establish a reduction between this setting and what they call the Recurrent Submodular Welfare (RSW), which entails maximising a monotone submodular function over $T$ steps, but where each element has a similar delay $d_i$ before it can be selected again. 

The RSW problem can be solved by a clever randomisation: rather than choosing each element with probability $1/d_i$, the authors interleave the elements by adding a random delay $r_i \in [0,1]$ and selecting the item whenever the interval [t/d_i + r_i, (t+1)/d_i + r_i] contains an integer. This simple step takes care of most of the inefficiency and the unknown time horizon $T$ is also handled: essentially, just the last step might be suboptimal and this effect decreases with $T$. This algorithm is optimal for this setting, with a $1-1/e$ approximation.

The full information setting can be handled by selecting arms a subset of arms that are available in the RSW case, but doing it greedily and stopping once an independent set is found, to satisfy that hard matroid constraints. The reduction is completed by using the weighted rank function, which converts an additive function with matroid constraints into a monotone submodular one. As such, this algorithm is also optimal with an approximation of $1-1/e$ (and some minor terms relating to $\max d_i$).

The final step into the bandit setting can be performed because the learning of the $\mu_i$ and the random selection of elements are decoupled: the RSW interleaving technique is ‘static’ and does not update its schedule as the algorithm runs. Therefore, a modification of UCB can be used to balance learning the $\mu_i$’s with exploiting them, while observing the schedule used by RSW. This also yields an optimal (1-1/e) approximation (with an additional  $O(k\sqrt{T \log T} + k^2  + \max d_i \cdot r)$ additive loss, where $r$ is the matroid rank).
main_review: The paper is very well written and provided an clear description of related work, in particular comparing with Blocking Bandits and Kleinberg and Immorlica [25], which also use a different interleaved rounding technique for a related setting where each arms ‘improves’ as it remains unused. Moreover, the authors have done a great job condensing the paper into 9 pages, with most of the intuition left intact.

The paper is technically strong, with the designed algorithms looking simple but containing subtleties that can be easily missed: there are many similar algorithms that almost work but are not optimal, which is what the authors claim as the main contribution of the paper. In terms of techniques, the authors have an interesting use of Convex Programming and the concave closure of a submodular function, both of which have received significant attention by the sumbodular community in recent years (although using the multilinear extension and rounding is more common).  The only criticism could be about the significance of the setting: why is it important to bridge the gap from $1-1/e^{0.5}$ (with a very simple algorithm) to $1-1/e$?

There are no experiments, which is could be ok for this type of paper, given that finding real data sets with matroid constraints and bandit feedback might be difficult. However, it would be nice to have some evidence (even on synthetic data) that the obvious algorithm is not as good in practice as the one designed here.
limitations_and_societal_impact: The authors have adequately addressed the limitations and social impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies an extension of the matroid bandit problem where each arm $i$ is blocked for a known $d_i$ rounds after it is played, and this is referred to as the matroid blocking semi-bandit (MBB) problem. When the arm distributions are known, the authors reduce the optimization problem to a recurrent submodular welfare (RSW) problem. The authors first propose a 1-1/e approximation to the RSW problem, then show that for MBB with unknown reward distributions, using the upper confidence bounds (UCB) instead of the known mean values would give a sublinear approximation regret with approximation ratio of 1-1/e. The main contribution of the paper is to achieve 1-1/e approximation, while an easy adaptation from some other work only gives 1/2 approximation.
main_review: The main contribution of the paper is to combine matroid bandit and blocking bandit to propose a solution to the matroid blocking semi-bandit problem, and it achieves 1-1/e approximation regret rather than the easier 1/2-approximation regret that could be obtained by some easier extension to some other work. Along the way, the authors define the recurrent submodular welfare problem and provide a 1-1/e approximation solution, and this could be of independent interest.

Technically, the algorithms proposed for RSW and MBB are based on some scheduling scheme, a technique used in the past studies. The online learning version uses the standard UCB idea. Overall, the paper presents an interesting problem with a nice solution. The intermediate problem of RSW is also interesting. The presentation is clean mostly. However, it is a bit unclear how much technical novelty is in the paper, since it seems that the results mainly come from several algorithmic ideas in the past.

More detailed comments:

- Line 47, "collects their sum". It is better explicitly say that "collects their sum as the reward for this round". Otherwise, it is unclear what is exactly the reward for each round.

- Line 101, what is $x_i$?

- Line 195, Theorem 1.4. It would be better if the authors also include the gap-dependent bound in the theorem.

- Line 212-213. The formula $f^+(x)$ has no explanation. Notations such as $1_S$ is not explained. What is the intuitive meaning of this function?

- Line 263-264, "For integral solutions, the above objective is equivalent to ...." Why is this so?

- Line 297, notation $\mathcal{X}$ is not explained.

- Line 298-299. Normally in online learning, "full-information" would mean that in every round the agent would receive feedback for all arms, but here "full-information" means that the arm distributions are known a priori. I believe the latter case is better called the offline setting, vs. the online learning setting.

- Line 336, using notation $\mathcal{R}$ to denote the randomness of the reward is confusing with the same notation used to denote the expected reward.

- Line 339. It is unclear to me why w.l.o.g we only focus on the case where the sequences of sampled arms are identical. What if they are not identical?

- Line 392 - 399. This paragraph needs some repeated reading to get the right idea. I guess what the authors mean is that MBB can be reduced to RSW, but the reverse may not be true, so MBB could have better approximation ratio, like having a PTAS. Also, throughout the paper, the authors often refer to MBB as an offline problem and talks about its approximation algorithm, while MBB is defined originally as an online learning algorithm. I guess sometimes the authors refer MBB with the known reward distributions. I suggest the the authors make the explicit distinction between the offline problem and the online problem, such as using MBB-offline to refer to the offline (full-information in their term) setting.

========= Post rebuttal comments ===============

I have read the authors' feedback and other review comments. As indicated in my review, my main concern is the technical novelty of the paper. The authors' response tried to address this, but it is still not entirely clear to me. However, in general, I think the paper has merit, and would like to encourage the authors to revise and further improve the paper, whether or not it is accepted at this conference.
limitations_and_societal_impact: The research is a theory work, and there is no perceived negative societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper focuses on matroid blocking semi-bandit and connected this problem to the problem of recurrent submodular welfare maximization.
main_review: 1) The author tried to motivate the subject from a theoretical and practical point of view, but they didn't add any simulation to show the performance of their method from a practical point of view.
2) In the introduction, the author reviewed the previous works. Still, related papers like [1] have not been appropriately discussed.
3)the author successfully addressed the issue and recommended the algorithm. 
4) The paper is well-organized and well-written.
5) The proof is mathematically correct.
[1]Chen, Lin, Andreas Krause, and Amin Karbasi. "Interactive Submodular Bandit." Advances in Neural Information Processing Systems 30 (2017).

----------- Post Rebuttal------------- 

I have read all the comments, and I don't change my score.
limitations_and_societal_impact: The authors discussed the limitations and potential negative social impact of their work.
review_title: null

Meta-review: This paper on bandits merged together many different aspects, submodularity on matroid, blocking bandits... 

We are not necessarily excited by papers that combine together exciting concepts, but this specific papers had other merits as the base offline problem is also not that trivial and requires different (new) techniques. 

Overall, the reviewers were all positive, the paper is well written, clear and easy to read. It can therefore be accepted at NeurIPS
Decision: Accept (Poster)