Recurrent Submodular Welfare and Matroid Blocking Semi-Bandits
Authors: Orestis Papadigenopoulos
Constantine Caramanis
Venue: NeurIPS 2021 Poster (2021)
Keywords: non-stationary
multi-armed
bandits
blocking
regret
submodular
welfare
maximization
approximation

Abstract: A recent line of research focuses on the study of stochastic multi-armed bandits (MAB), in the case where temporal correlations of specific structure are imposed between the player's actions and the reward distributions of the arms. These correlations lead to (sub-)optimal solutions that exhibit interesting dynamical patterns -- a phenomenon that yields new challenges both from an algorithmic as well as a learning perspective. In this work, we extend the above direction to a combinatorial semi-bandit setting and study a variant of stochastic MAB, where arms are subject to matroid constraints and each arm becomes unavailable (blocked) for a fixed number of rounds after each play. A natural common generalization of the state-of-the-art for blocking bandits, and that for matroid bandits, only guarantees a $\frac{1}{2}$-approximation for general matroids. In this paper we develop the novel technique of correlated (interleaved) scheduling, which allows us to obtain a polynomial-time $(1 - \frac{1}{e})$-approximation algorithm (asymptotically and in expectation) for any matroid. Along the way, we discover an interesting connection to a variant of Submodular Welfare Maximization, for which we provide (asymptotically) matching upper and lower approximability bounds. In the case where the mean arm rewards are unknown, our technique naturally decouples the scheduling from the learning problem, and thus allows to control the $(1-\frac{1}{e})$-approximate regret of a UCB-based adaptation of our online algorithm.

Recurrent Submodular Welfare and Matroid Blocking Semi-Bandits
Orestis Papadigenopoulos
Constantine Caramanis Electrical and Computer Engineering The University of Texas at Austin constantineCutexaa edu
Department of Computer Science The University of Texas at Austin papad gâcs utexas.
Abstract
A recent line of research focuses the study of stochastic multi-armed bandits (MAB), in the case where temporal correlations of specific structure are imposed between the player's actions and the reward distributions of the arms. These corre- lations lead to jopti)l solutions that exhibit interesting dynamical patterns challenges both from algorithmic well
phenomenon that yields a learning perspective. In this work, we extend the above direction to a combi- natorial semi-bandit setting and study variant of stochastic MAB, where arms are subject to matroid constraints and each arm becomes unavailable (blocked) for fixed number of rounds after each play. A natural common generalization of the state-of-the-ar for blocking bandits, and that for matroid bandits, only guarantees //2-approximation for general matroids. In this paper we develop the novel technique of correlated (interleaved) scheduling, which allows us to obtain polynomial (1 "tpeaaappxxiittion algorithm (asymptotically and expectation) for any matroid. Along the way, we discover an interesting connection a variant of Submodular Welfare Maximization, for which we provide (asymp- totically) matching upper and lower approximability bounds. In the case where the mean arm rewards are unknown, our technique naturally decouples the scheduling from the learning problem, and thus allows to control the (1 -pp)-approximmte regret of UCB-based adaptation our online algorithm.
Introduction
Despite the large number of variants of the stochastic multi-anae aaetid-rrmeddde bandits (MAB) model that have been introduced 8 sd) the majority of the results comply with the common assumption that playing an action does not alter environment, namely, the reward distributions rounds (with notable exceptions discussed below). Only recently, researchers have focused their attention on settings where temporal dependencies of specific structure are imposed between the player's 's actions and the reward distributions 127 10 consider the setting of recharging bandits, where the expected reward of each arm is a concave and weakly increasing function of the time passed since its last play, modeling in that way scenarios of local performance loss. In a similar spirit, Basu et al. ? consider the problem of blocking bandits, in which once arm is played at for a fixed number of consecutive rounds. Notice that all the aforementioned examples are variations of the stochastic MAB setting, where the decision maker plays (at most) arm per time step.
subsequent
39
6
In (27. Kleinberg and Immorlica
round, cannot be played again (i.e., it becomes blocked)
When combinatorial constraints and time dynamics come together, the result is much richer and more challenging setting, preciscly because their interplay creates complex dynamical structure. Indeed, the standard combinatorial bandits setting [T, the optimal solution in hindsight is to consistently play the feasible subset of arms of maximum expected reward. However, in the presence
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

of local temporal constraints on the arms, an optimal (or even suboptimal) solution cannot be trivially characterized- a fact that significandly complicates the analysis. both from the algorithmic as well as from the learning perspective. In this work, we study the following bandit setting- common generalization of matroid bandits, introduced by Kveton et al. [30, and blocking bandits 77]
(MBB)). We consider a set A of k arms, a matroid M = (A, and an unknown time horizon of T rounds. Each arm i E AA is associated with an unknown bounded reward distribution of mean pú, and with a known deterministic delay d, such that whenever an action i is played at some round, it cannot be played again for the next d, 1 rounds. At each time step, the player pulls a subsel of the available (i.e., not blocked) arms restricted to be an independent set of M. Subsequently, she observes the reward realization of each arm played ssemi-bandii feedback) and collects their sum as the reward for this round. The goal of the player is to maximize her expected cumulative reward over T rounds.
Problem 1.1 (Matroid Blocking
The above model captures a number of applications, varying from team formation to ad placement, when arms represent actions that cannot be played repeatedly without restriction. As concrete example, consider a recommendation system that repeatedly suggests variety of products (e.g.. songs, movies, books) to a user. The need for diversity on the collection of suggested products (arms), to capture different aspects of user's preferences, can be modeled as linear matroid. Further, the blocking constraints preclude the incessant recommendation of the same product (which can be detri- mental, as the product might be perceived as "spam"), ") while the maximum rate of recommendation (controlled by the delay) might depend on factors such as popularity, promotion and more. Finally, the expected reward each product is the probability of purehasing (or clicking).
From a technical viewpoint, the MBB problem is already NP-hard for the simple case of uniform rank-1 matroid (see Theorem 2.1 in [33 even in the full-information setting, where the reward distributions are known to the player a priori. The natural common generalization of the algorithms in 7 BC computes and plays, each time step, an independent set of maximum mean reward consisting of the available elements. While the above strategy is a (1 - 1/e) -approximiainnnn asymptotically (that only guarantees a 1/2-approximation for
is, for T + 20) for partition matroids, unfortunately,
general matroids [ and this guarantee is tight (see Appendix E for an example). A natural question that arises is whether a (1 1/e) approxiaiiii is possible for any matroid.
The main result of this paper shows that this is indeed possible. Along the way. we identify that the key insight (and also the weak point of the naive 1/~-approximationn is the underlying diminishing returns property hidden in the matroid structure. In particular, we discover an interesting connection of MBB to the following problem of interest in its own right:
Problem 1.2 (Recurrent Submodular Welfare (RSW)). We consider a monotone (non-decraasing) submodular function f 2 + Rzo over a universe A and a time horizon T. At each round t E [T] we choose a subset A. S. A and collect a reward (Ar). However, using an element E A at some round L E [T] makes il unavailable (i.e. blocked) for a fixed and known number of d; 1 subsequent rounds, namely, during the interval [1,++d;-1) The objective is to maximize Eie(r) [(Ar), subject to the blocking constraints, within a (potentially unknown) time horizon T.
For the above model, which can be thought of as a variant of Submodular Welfare Maximization we provide efficient randomized (1 - -pppooppoxinnno (asympiotically), accompanied by matching hardness result. Note that the RSW problem is very natural model, capturing applications of submodular maximization in repeating scenarios, where the elements cannot be constantly used without restriction. As an example. consider the process of renting goods to a stream of customers with identical submodular utility functions modeling their satisfaction.
As we show, our approach for the RSW problem immediately implies an algorithm of the same approximation guarantee for the full-information case of MBB and, additionally, it has important implications for the bandit setting, where the reward distributions are initially unknown. The standard goal in this case is to provide a (sublinear in the time horizon) upper bound on the regret, namely, the difference between the expected reward of a bandit algorithm and a (near-) )ottial algorithm, due to the initial lack of knowledge of the forme
In fact, we upper bound the (1- (11-3%))(approonn (approximate) regret, detined as the difference between (1 1/e) OPT(I') and the expected reward collected by a bandit algorithm. The notion of a-regret is widely used in the combinatorial bandits literature [15 48 for combinatorial problems where efficient algorithm

---

1.1 Related Work
recent line of research focuses on non-stationary models the case where each reward distribution is a special function of the player's actions [IO 39 G In 77. Basu et al. provide greedy (1 - 1/-)- approximation for the full-information case of the blocking bandits problem (a special case of the MBB model for uniform rank-1 matroid). As we have already mentioned, generalizing their strategy to the MBB problem fails to provide the same guarantce for general matroids. In the bandit setting, where the reward distributions are initially unknown, the authors have to overcome the burden of characterizing a (sub)optimal solution, where the rate of mean collected reward exhibits significant fluctuations over time. The key insight is to observe that every time the full-information algorithm plays an arm, its bandit variant, which relies on estimations of the mean rewards, has at least one chance of playing the same arm. However, this key coupling argument, that enables sublinear regret bounds, becomes significantly more involved in the presence of matroid constraints.
In 27 Kleinberg and Immorlica study the case of recharging bandits. Their approach first computes the "optimal" playing frequency 1/x; of each arm i via a mathematical formulation. In order to play each arm with this frequency, they develop the technique of interleaved rounding, where they associate each arm i with a sequence of real numbers 3.. with a; ~ U[O, 1]. Then, the arms are played sequentially in the same order they appear on the real line. This novel rounding technique exhibits reduced variance and, thus, an improved approximation guarantee comparing to other natural approaches such as independent randomized rounding.
The MBB model is also related to the literature on periodic scheduling consider the problem of periodically scheduling jobs on a set of machines. Each job is associated with a processing time, during which it occupies the machine minimum time required after its completion in order to be rescheduled, and a reward. It not hard to see that the case of unit processing times is a special case of MBB with a uniform matroid of rank equal to the number of machines, under the objective of maximizing the total reward. Further, it is known i that the rank-1 case of MBB generalizes the Pinwheel Scheduling problem [4]]: Given k colors associated a set of integers {d, hee[M] such that ΣielK] 1/d, 1, decide whether there is coloring of the natural numbers N > [k] such that every color E [4] appears at least once every d, numbers. As it is proved in [25 the above problem does not admit a pseudopolynomial time algorithm unless SAT can be solved by a randomized algorithm in expected quasi solss--polyooiill time.
Sgall et al.
executed on, a vacation time, namely, a
In a concurrent work M. the authors consider the blocking bandit model in a generic combinatorial setting and under stochastic delays. As they show, the greedy algorithm that plays at each time the maximum feasible subset of available arms is a ((1) apprrxiiooinnnoonnn for downward-closed set systems. However, when specialized to matroids, they cannot do better than a 1/2-approximation We need new ideas to reach a (1 2/e) approximationn algorithm and associated regret guarantees for the rich class of matroid bandits.
Our work is related to the line of research regarding bandit optimization of submodular functions (see [ 20 and references therein). We refer the reader Appendix A for additional related work on non nta-sstatooary bandits, combinatorial bandits, and submodular welfare maximization.
1.2 Our Contributions
Reducing full-information MBB to RSW. We first focus on the full-information variant of MBB, where the mean rewards of the arms are known to the player priori. We assume that the player has access to the matroid M via an independence oracle and knowledge of the arms' fixed delays, yet she is oblivious to the time horizon T. In this sense, she plays online. An interesting aspect of dynamics, as illustrated in [27 m d is that one needs to guarantee, via scheduling, that each arm is roughly played at a frequency close its "optimal" rate. This is particularly important in the presence of "hard" blocking constraints, where no reward can be obtained by a blocked arm.
In order to address the above scheduling problem, we propose a particular "decoupled" two-phase strategy. We refer to each phase as (cooperative) Player and Player B. Initially, Player A decides on a schedule that determines arm availability, namely, subset of rounds where each arm is allowed to be played. Subsequently, Player chooses a subset of available arms that maximizes the total
does not exist, and, thus, any efficient algorithm would inevitably suffer linear regret in standard definition (where = 1).
3

---

expected reward, subject to the matroid constraints. In order to completely decouple the two phases, the availability schedule produced by Player A is never affected by which arms are eventually chosen by Player B (that is, it is impossible for Player B to violate the blocking constraints).
In the case where Player knows the expected rewards of the arms and due to the above decoupling property, his optimal strategy (given any availability schedule) can be easily characterized: Since the arms of each round are subject to matroid constraints, Player B achieves his goal by playing maximum expected reward independent set among the available arms of each round, which can be computed efficiently using the greedy algorithm for matroids. Thus, the role of Player A becomes to choose an availability schedule that maximizes the total reward, knowing that Player B will behave exactly as described above. The key observation that the solution computed by Player B each round, corresponds to the weighted rank function of the matroid evaluated on the set of available arms of the round. More importantly, it can be proved that this function monotone submodular and, hence, Player A's task is a special case of the RSW problem.
Optimal approximation for RSW. Focusing our attention on the RSW problem, any "good" solution should guarantee that each element i E A is selected a fraction of the time close to 1/d; (the maximum possible), where d, is the delay. However, naive randomized approach that selects (if available) each element i with probability 1/d, independently at each round, can be as bad as a (1 - e- e-1/2) s 0.393-approximation (see Appendix D for an example). Instead, motivated by the rounding technique of Kleinberg and Immorlica (27], we develop a jimee-ccorreltte sampling strategy, which we call interleaved scheduling. While our technique is based on the same principle of transforming (randomly interleaved) sequences of real numbers into a feasible schedule, our implementation is very different. Indeed, as opposed to [27] we additionally face the issue of scheduling more than one arms per round, subject to matroid constraints, and the fact that our "hard" blocking constraints are particularly sensitive to the variance of the produced schedule. Using our technique, we construct polynomial-tine randomized algorithm, named following guarantee for RSW:
(IS), that achieves the
Theorem 1.3. The expected reward collected by INTERLEAVEDDSSUMOODUE
over T rounds, (T),, is at least (1 - 1/c) OPT(T) (ddmax (A)), where OPT(T) is the optimal reward of RSW for T rounds and dmax = m d; is the maximum delay of the instance.
The proof of the above guarantee relies on the construction of a convex program (CP), based on the concave closure of f (see below), that yields an (approximate up to an additive term) upper bound on the optimal reward. Although our algorithm never computes an optimal solution this convex program, it allows us to compare its expected collected reward with the optimal solution of CP, leveraging known results on the correlation gap of submodular functions. As we show via a reduction from the SWM problem with identical utilities, the (1 - (1/)) term in the above guarantee is asymptotically the best possible, unless P = NP; further, the additive term results from the fact that our algorithm is oblivious to the time horizon T.
Bandit algorithm and regret guarantees. We now turn our attention the bandit setting of MBB, where the mean rewards are initially unknown. Our interleaved scheduling method exhibits an additional property: It does not rely on the monotone submodular function itself, a fact that is particularly important for the bandit setting. Indeed, in the full-information setting Player B computes a maximum expected reward independent set each round, for any availability schedule provided by Player A. In the bandit setting, however, the reward distributions are not priori known and, thus, must be learned. Nevertheless, we do not need to wait to learn these distributions to find a good availability schedule. This allows us to make natural coupling between the strategy of Player B in the bandit and in the full-information case and, thus, to compare the expected reward collected "pointwise", assuming a fixed common availability schedule. We remark that the above coupling is very different than the one in 7 as ours is independent of the trajectory of the observed rewards.
The above analysis allows us to develop bandit algorithm for MBB based on the UCB method, called INTERLEAVED-UCH (IB). Specifically, given any availability schedule provided by Player A (independently of the rewards) and in increasing order of rounds, Player B greedily computes a maximal independent set consisting the available arms of each round, based on estimates (known as UCB indices) of the mean rewards. In order to analyze the regret, we use the independence of the availability schedule in combination with the strong basis exchange property of matroids. This allows us to decompose the overall regret of our algorithm into contributions from each individual arm.

---

Once we have established this regret decomposition, we can bound the individual regret attributed to each arm using more standard UCB type arguments [00, leading to the following guarantee:
Theorem 1.4. The expected reward collected by INTERLEAVED- -UCB in rounds, T (T), arms, matroid of rank rk(M) and maximum delay duax is at least
(T), for
1 -1- OPT(T) O (KVTTIIITT + k2 dmaxx)
In the above bound, the additive loss corresponds to the regret with respect (1-3) 1) OPT(T). Interestingly, our regret bound is very close (even in constant factors) to the cnpommttion-teoreiiinn optimal bound provided in [60 for the non-blocking setting. In fact, except for the small additive (dmaax)) term, the regret bound in [30] is the same as ours, if we replace the number of arms with vk r. Intuitively, this is due to the fact that our algorithm must learn the complete order of mean rewards, as opposed the non-blocking setting where learning the maximum expected reward independent set in hindsight is sufficient for eliminating the regret.
All the omitted proofs of results have been moved to the Appendix.
2 Preliminaries Matroids and Submodular Functions
Continuous extensions and correlation gap of submodular functions. Consider any set function
f:24 R>0 over ground set A. Recall that f is submodular, if VS, T' A we have f(S ( f(S ((S) + f(T).. For any point x E [0, 1J we denote by S x the random set S S A. such that IP (i S) = Ti. We consider two canonical continuous extensions of a set function:
Definition 2.1 (Continuous extensions). For any set function f the multi-linear extension
F(x) E [f(()]
Σ
f(S)
II 24 [1
SCA
IES
igS
Moreover, the concave closure is defined
ft (x) = max f Σ aas((S)
Σ
agls xx
Σ 1,a a,
SEA
SCA
SCA
where 1s E {0, 11 is an indicator vector such that (1s): 1, e S, and (1g); = 0, otherwise.
Lemma 2.2 (Correlation gap 1.. Let J : 2* + Rzo be a monotone (non-decreasing) submodular
function. Then for any point x [0, 1] we have
F(x) S (1- F(x).
Matroids and weighted rank functions. Consider a matroid M = (A, where A is the ground set and I is the family of independent sets. Recall that in any matroid, the family I satisfies the following two properties: (i) Every subset of an independent set (including the empty set) is an independent set, namely, if S' S C A and S I, then S' E I (hereditary property). (ii) Let S. C A be two independent sets with |S] < S then there exists some e E S such that SU [e} E I (augmentation properry). See 4p 37 for more details matroids.
We assume that access to M is given through an independence oracle 122 namelyy a black-box routine that, given set S C A. answers whether S' is an independent set of M. For any set R C A we define the restriction of M to R, denoted by M R. to the matroid M (R, (T I I R)).
Given any non-negative linear weight vector w R the problem of computing maximum weight independent set can be solved optimally by the standard greedy algorithm: Starting from the empty set S = 0, add each ground element AA to the set S in non-increasing order of weights, long as the set S U {e} does not contain a circuit. Given a matroid M = -A, and a weight vector w, the function fM. (S) maxIet,Içs (w[]) } is called the weighted rank function of M and returns the weight of the maximum independent set of the restriction M M.
Lemma 2.3 (Weighted rank function
M1) For any matroid M and non-negative weight vector w,
the function f.,.((S) (S) = (w is monotone (non-decreasing) submodular.
5

---

Technical notation. For any event E, we denote by X (E) E {0. the indicator variable such that X (E) if & occurs, and X (E) 0, otherwise. For any non -eg-atite integer n E N, we define [n] = (1.2....... n2.. For any vector μ E Ie and set S S [k]. we define y(S) Dies P4 Moreover, the notation & [a, bj (for a S b) for some time index in place of t E [T] [a,...... (a........ .b. Unless otherwise noted, we use the indices i, j or to refer to arms and t, t' or r to refer to time. Let Ar E I be the set of arms played by some algorithm E {1S, IG, IB] (defined in Sections 3 and at time L. Unless otherwise noted, all expectations are taken over the randomness of the offsets (ra) (see Section and the reward realizations.
3 Recurrent Submodular Welfare
Let ʃ(S) 2 ++ R2o be a monotone submodular function over a universe A of elements, such that f(0) 0. In the blocking setting, each element E AA is associated with known deterministic delay d, E Nyo. such that once the arm is played at some round t. it becomes unavailable for the next d; rounds, namely, in the interval {t....,t t + d; 1}. At each round t [7], the player chooses a subset At of available (i.e., non-blocked) elements and collects a reward f (AA).. The goal is to maximize the total reward collected, i.e., EiEny (A)), within unknown time horizon T.
We provide an efficient randomized (1 approxxproinnaooonn algorithm for RSW. Informally, the algorithm starts by considering, for each element i E A. a sequence of rational numbers of the form {t- ये hE(T)- Then, these sequences are interleaved by randomly adding an offset ri, drawn uniformly at random from [0, 1], for each i E to the corresponding sequence. At every round E [T), the algorithm chooses set Ar. consisting only of elements for which the (perturbed) interval Lit - [1- J, + ri; (4 + 1)- ग. + r.) contains an integer.
Algorithm 3.1 (INTERLEAVED SEEEED--SUMMULLLEE (IS)). For each element i E A. let r, ~ U[O, 1] be a random offset drawn uniformly from [0. L]. At every round of elements such that for any E As, the interval Li,t = [t 1 + Te. (t 1) d. + +r/) contains an integer. Choose the elements A, and collect the reward ((As).
1,2,..... let A, S A be the subset
d.
3.1 Correctness and approximation guarantee.
We first show the algorithm is correct, namely, that the elements chosen at each round respect the blocking constraints. The correctness established by the following simple observation:
Fact 3.2. At any E (T), all the elements in At are available (i.e., not blocked).
In order prove the competitive guarantee of our algorithm, we first construct convex programming (CP)-based (approximate) upper bound on the optimal reward. Although our algorithm never computes an optimal solution to this CP, this step allows us prove our guarantee, leveraging results on the correlation gap of submodular functions. For d-1 E R such that (d- = 1/d,, vi E [k]. consider the following formulation based on the concave closure f of f:
maximize: T fff((z) xERk
s.t. 0 0
(CP)
In (CP) each variable 2 can be thought of as the fraction of rounds where element i E A is chosen. Intuitively, the constraints indicate the fact that, due to the blocking, each element i E A can be played at most once every d, steps. In order to derive (CP), we start from non-convex integer program (IP) with 0-1 variables (ai.:]vEA..ET)) each indicating whether element i E A is used round E [T]] The objective is maximize EiETT EScA f(S) ILiS Ti.t Iligs (1 x;,)) subject to natural blocking constraints. For integral solutions, the above objective equivalent to Eie(r) f (xx) (where (x:); = zx,z) and, thus, the above relaxation is simply the result of averaging over time the variables and constraints of this IP. By using the concavity of st, we are able to show that (C) yields an (approximate) upper bound on the optimal solution of RSW, while the approximation becomes exact as T increases.
Lemma 3.3. Let CP (T) be the optimal solution CP and OPT(T) be the optimal solution over T rounds. We have RCP (T)= 2 OPT(T) Od (AA), where dmax maxie (d:)-
Before we complete the proof of our first main result, we first compute the probability that i E Ar. ic., element E A is sampled at round t E [T]:

---

Fact 3.4. For any i E A and E [T]. we have P E A.) P (L., N N 0) -/d..
Proof of Theorem 1.3 Let us denote by S ~ P with E [0, 1| the random set S S A. where each element participates in S indeeendennly with probability equal to p;. By Fact F.4t and due to the randomness of the offsets (ri). we have that Ar ~ d-1 for each f E (T]. Let x be an optimal solution to CC). By monotonicity of f and the fact that z= ===a d for the expected value of {AA)
at any round & E [ we know that E
[f(A.) 2 E
[f(A,)] Moreover, by definition of the
A
A.
multi-linear extension, we have that E
[f(AA)] = F F(zz) ) while by Lemma 2.2 (the correlation
Acna"
gap of submodular functions), we have that, F(z) 2 (1 - 2 ft (z) for any vector z E [0, 1]k. By combining the above facts, we can see that
(1 T (+(²x) = (1- R-
R (T)(T)) = Σ
[S(AN) 2 Σ F(2)
RCP(TT)
[E[T] A
EE[T]
Therefore, by Lemma 3.3 we can conclude that R (T) 2 (1 OPT(T) - ( 11
In Appendix we provide a (1 Weeahhaddesss result for RSW, thus proving that the guarantee of Theorem 3 IS asymptotically tight. This result, which holds even for the special case where dmax o(T) (that is when the delays are significantly smaller than the time horizon), is proved via a reduction from the SWM problem with identical utilities, way that the constructed RSW instance accepts w.l.o.g. solutions of a simple periodic structure.
Theorem 3.5. For any e > O, there exists no polynomial-time (1- - - -pp-roxpaaiattatii algorithm for the RSW problem, unless P NP, even in the special case where dmma = o(T).
a.
4 Matroid Blocking Semi-Bandits
Let A be set of is arms and T be an unknown time horizon. At any round E [T] and for each i A reward Xt,, is drawn independently from an unknown distribution mean μr and bounded support in [0, 1]. Let d, No.0 be the known determinisite delay of cach arm E A. and dmax max } At any round E [T]. the player pulls any subset A, of the available (i.e., non-blocked) arms, as long as it forms an independent set of a given matroid M (A, I). The player only observes the realized reward of each arm she plays and collects their sum. The goal is to maximize the expected cumulative
reward collected within T rounds, denoted by R.C (T)
Eietry EIEA X1, X (i E At)
The full-information setting The following algorithm is the implementation of IS in the special case of the full-informttin MBB setting, where the mean rewards {usieed hia are known a priori:
Algorithm 4.1 (INTERLEAVED- SEEBLEAVED--REED (IG)). For each arm E A, let r; ~ U00, 1] be a random offset drawn uniformly from [0, 1]. At every round t = 1,2,..., let G. S A be the subset of arms i E A, such that the interval L,, = It I + Ti, (t + 1) J. + rr) contains an integer. Greedily compute a maximum independent set Ar of M G. with respect to { hes, and play these arms.
The following result is an immediate corollary of Theorem 1.3 given that the value of the greedily computed maximum independent set in MM| G. corresponds to the weighted rank function fM, which, by Lemma 3 is monotone submodular:
Theorem 4.2. The expected reward collected by INTERLEAVED-GREEDI for T rounds, R (T),
at least (1 ()) OPT(T) Oddmax rk(M)), where OPT(T) is the optimal expected reward.
Remark 4.3. The analysis of 1G is tight for rank-1 matroids. Indeed, consider k arms, each of delay k and deterministic reward equal to 1. For T - oo, the optimal average reward equal to 1, simply by playing the arms in a round-robin manner. However, the probability that al least one arm is sampled at some round is Σ
5m1 (9 (1-)) -1)===1----
t)*
+ 1 as k - oc.
The bandit setting and regret analysis In the setting where the mean rewards are initially un- known, we develop UCB-based bandit algorithm, INTRRLEAVED-UCK (IB). The algorithm identical to IG, except for the greedy computation of the maximum independent set over the sampled
7

---

arms, which is now performed using estimates. Specifically, the algorithm maintains for every i E A. t e [T] the following upper estimate of p4
2 In (1) Pi. (..T.(0) CLet with CiA1 V (t())
where T(( denotes the number of times arm has been played at the beginning of round / and (1) denotes the empirical average of the Ti(l) i.i.d. samples from its reward distribution. The term Ct2 is the confidence length around (t)) that guarantees Fi,t lies in [p4, P4 + 2c,,,] with high probability. Note that all the above quantities are random variables depending on the random offsets and the observed reward realizations.
We are interested in upper bounding the a-regret, for a = -1 namely, the difference between (TP and the expected reward collected by IB. Due to the complex time dynamics, characterizing the optimal expected reward as a function of the instance is hard. However, using Theorem 4.2 we can upper bound QOPT(T) by the expected reward collected by IG, thus giving:
aTPT(T) - RUCB (T) S RTO( (T) R (T) + Oddmax rk(M)).
By the above inequality, it becomes clear that order to upper bound the regret, it suffices to bound the difference between the expected reward collected by IG and IB. This difference not only depends on the reward realizations (through the UCB estimates), but also on the trajectory of sampled arms in each algorithm, which is itself function of the random offsets. However, by construction of our interleaved scheduling scheme, these offsets are sampled at the initialization phase of each algorithm and are identically distributed. Thus, the trajectories of sampled arms in the two algorithms exhibit coupled evolution. This allows us to analyse the regret "pointwise", under the assumption that the sequences of sampled arms are identical throughout the time horizon. To make this idea precise, let r E [o, 1]at be the random offsets used and let {g: (r")) heerr be the sequence of sampled arms by algorithm æ E {TG, B).. Using (henceforth) Q to denote the randomness due to the reward realizations of the arms, the next lemma gives pointwise regret bound.
Lemma 4.4. Let (e( = Eies is and p(5) Eies Mb. We have
R (T)(T)) - (T)
E
Σ [E[T]
(n(3) - SCG.(r),SEI
max
-MarE aar max SCC.(r).SET
e
Thus w.l.o.g., we focus on the case where the sequences of sampled arms are identical. Let & denote the event that both algorithms, IG and IB, sample the same offset vector r, namely, r JG = =r' Assuming that &, holds for some r [0, 1] let {9theer sampled arms, common in both algorithms. Clearly, IB accumulates regret only when it plays independent sets of arms that are suboptimal w.r.t. the true means, i.e., when () < m(A!C) ) for some E [T]. We assume w.l.o.g. that the arms are indexed in decreasing order of mean rewards and that these mean rewards are distinct. We now formally define the gaps related to our analysis:
{r)(T) be the sequence of
Definition 4.5 (Gaps). For any subset S C A and reward vector IR we define
As(v) max (n(1)) - arg BEIS
max Av (B))
IEI,gS
Moreover, let Aij = p4 H4 be the standard suboptimality gap between arms i,j E A.
By Lemma 4.4 and assuming that the event & holds for some r, we are interested in bounding the expectation of 2 (Rt) w.r.t. the reward realizations. The next step is to decompose the suboptimality of IB by noticing that both algorithms play, at each round t [T]. a basis of M G. and thus ! A! We use the following fundamental property of matroids:
|
Theorem 4.6 (Strong Basis Exchange. Corollary 39.12a in (42)). Let M (A,I) be a matroid and I1, 12 I be two independent sets such that [ = [2). Then, there exists a bijection 11 - 12, such that for any E In the set I - i (i) is an independent set of M.
Let oe A. + AIG for each [T'] be the bijection described in Theorem 4.6 with respect to the sets AB and A and let o, be its inverse mapping. Note that in any bijection oe and any i E A! nAG we can assume w.l.o.g. that (i) = i. Notice, further, that under the event &,, the bijections (ar herre are still random variables that depend on the observed realizations.
8

---

Lemma 4.7. Under the event &, and at any time t E [T], we have (p, = Eierio A (
Conditioned on the fact that both algorithms operate on the same sequence (Gr of sampled arms, Lemma 4.7 allows us decompose the suboptimality gap Ag, (āt) of each round E [T], into simpler gaps of the form A.jj between any arms i A! and A! that are perfectly matched according to the bijection implies that i A! and j E A we can further upper bound the regret as
namely, oz(i) = i. Assuming that the event {or(i) = i} directly
EAs. Ag. FE|21
C A,r'00 SEA!
E E AETT JEA.A.,>00
An X (o.(1)
The above inequality allows us to study the regret attributed to each arm independently, using more standard arguments for UCB-based algorithms combination with Theorem 4.6 Specifically, for every pair of arms i.j A with i (thus, A., 0), we define threshold E., with the following key-property: After IB "exchanges" arm j for arm oz(j) more than li,5 times, due to insufficient exploration, then it has collected enough samples infer that p4 < μa with high probability.
Lemma 4.8. Let lis-
8 (l((T) 2
for any j. Under event &, and for any arm we have
E (E[T]
Ar, (0, ((a)s
A1- IT)
16
(Under-sampled regret) (2)
n S
E
45)
(Sufficiently sampled regret) (3)
EE
By inequality 1 and Lemma in order to bound the regret of IB, conditioned on the fact exactly the same offset vector and, thus, they operate the exact same sequence sampled arms, denoted by herre By construction, IG plays at any round E [T] basis of MM| G. of maximum expected reward, while IB plays basis of M G. that maximum with respect to the estimates (ia.iie By Theorem 4.6 we can consider perfect matching between exchangeable arms of A and A! and, thus, decompose the regret into suboptimality gaps between individual arms. Then, using Lemma 4.8, we can upper bound on the expected regret due the fact that IB erroneously plays arm j instead of arm i, when Di.j O. The above analysis culminates in the following gap-dependent regret upper bound:
Proof sketch of Theorem 1.4
suffices to upper bound the difference between R (T) and R R²"(T), (T). that both algorithms
16
Σ J>1
In
Σ Aij O(dmax rk(M)) (gap-dependent regret).
==1
In order to derive a gap-independent regret bound, we partition the gaps into "small" and "large" and notice that any pair of arms j,j E A with A., < @(V T cannot contribute more than / In (T)
In(T)
loss in the regret.
Conclusion and Further Directions
We explore the effect of action-reward dependencies the combinatorial MAB setting by in- troducing and studying the MBB problem. After relating the problem to RSW, provide (1 - 1/pa-oaioooioiaaiiinn for its full-information case, based on the technique of interleaved schedul- ing. Importantly, our technique is oblivious to the reward distributions of the arms- fact that allows us to provide regret bounds of optimal dependence in T, when these distributions are initially unknown. We believe that this idea could be further applied to different classes of (combinatorial) non-stationary bandits, other than blocking bandits.
Our work leaves behind numerous interesting questions. By exhaustive search over (11)-periodic schedules, one can construct PTAS for the (asymptotic) MBB problem, assuming constant rk (M) and (d kE())- It remains an open question, however, whether the (1 apprroxppooiiiaiionn is the

---

best possible in general. We remark that the hardness of MBB cannot solely rely on an argument similar Theorem B.5 since the welfare maximization problem for the class of gross substitutes, which includes weighted matroid rank functions, is easy 35 Finally, it is easy to show that our algorithm gives a (11) aapprxxmmmtioonnn for the case of stochastic delays. Whether we can recover a (1 approxxpooinnnnoonn in this case is an interesting open question.
Acknowledgements
The authors would like to thank an anonymous reviewer of a previous version of this work for an unusually thoughtful and helpful review, which aided us in improving the document in particular, for pointing out the idea of correlated rounding. Further, the authors would like to thank Jannik Matuschke for noticing that the weighted matroid rank function falls into the class of gross substitutes.
Funding Transparency Statement
This research was partially supported by NSF Grant 2019844. In addition, this research was sponsored by the Army Research Office and was accomplished under Cooperative Agreement Number INF- 19-2-0333. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References
[1] A. Atsidakou, O. Papadigenopoulos, S. Basu, C. Caramanis, and S. Shakkottai. Combinatorial blocking bandits with stochastic delays. In Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 404-413.
PMLR, 18-24 Jul 2021.
[2] Auer, Cesa-Bianchi. and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3):235-256, May 2002.
[3] A. Badanidiyuru, R. Kleinberg, and A. Slivkins. Bandits with knapsacks. J. ACM, 65(3), March 2018.
[4] A. Bar-Noy, R. Bhatia, Naor, and B. Schieber. Minimizing service and operation costs of periodic scheduling. Mathematics of Operations Research, 27(3):518-544 2002.
[5] A. Bar-Noy, R. E. Ladner, and T. Tamir. Windows scheduling as a restricted version of bin packing. ACM Trans. Algorithms, 3(3):28-es, August 2007.
[6] S. Basu, O. Papadigenopoulos, C. Caramanis, and S. Shakkottai. Contextual blocking bandits. In International Conference on Artificial Intelligence and Statistics, pages 271 271-279. PMLR, 2021.
[7] S. Basu, R. Sen, S. Sanghavi, and S. Shakkottai. Blocking bandits. In Advances in Neural Information Processing Systems (NeurIPS) 32, pages 4785-4794. Curran Associates, Inc., 2019.
[8] S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Machine Learning. 5(1):1-122, 2012.
[9] G. Calinescu, C. Chekuri, M. Pál, and Vondrák. Maximizing a submodular set function subject matroid constraint (extended abstract). In Matteo Fischetti and David P. Williamson, editors, Integer Programming and Combinatorial Optimization, pages 182-196, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.
[10] L. Cella and Cesa-Bianchi. Stochastic bandits with deley-de payoffs. Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Confer- ence on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1168-1177, Online, 26-28 Aug 2020. PMLR
10

---

[11] N. Cesa- Desa-Bianchi and G. Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 7804):1404 1422. 2012. JCSS Special Issue: Cloud Computing 2011.
[12] L. Chen, A. Gupta, and J. Li. Pure exploration of multi-armed bandit under matroid constraints. Proceeding of the 29th Annual Conference on Learning Theory (COLT 2016), 2016.
[13] I.. Chen, Krause, and A. Karbasi. Interactive submodular bandit. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[14] W. Chen, W. Hu, F. Li, J. Y. Liu, and P. Lu. Combinatorial multi-armed bandit with general reward functions. In Proceedings of the 30th International Conference Neural Information Processing Systems, NIPS' 16, page 1659-1667, Red Hook, NY, USA, 2016. Curran Associates Inc.
[15] W. Chen, Y. Wang, Y. Yuan, and Q Wang. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. J. Mach. Learn. Res., 17(1):1746-1778 January 2016.
[16] R. Combes, C. Jiang, and Srikant. Bandits with budgets: Regret lower bounds and optimal algorithms. In Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Compuler Systems, SIGMETRICS '15 page 245-257, New York, NY, USA, 2015. Association for Computing Machinery.
[17] R. Combes, M. S. Talebi, A. Prouticre, and M. Lelarge. Combinatorial bandits revisited. In Proceedings of the 28th International Conference Neural Information Processing Systems Volume 2, NIPS' 15, page 2116-2124, Cambridge, MA, USA, 2015. MIT Press.
[18] U. Feige and J. Vondrák. The submodular welfare problem with demand queries. Theory Comput., 6:247-290, 2010.
[19] J. C. Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society, Series B, pages 148-171 177, 1979.
[20] D. Golovin and A. Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Artificial Intelligncce Research, 2011.
[21] S. Guha, K. Munagala, and P. Shi. Approximation algorithms for restless bandit problems. J. ACM, 58(1), December 2010.
[22] D. Hausmann and B. Korte. Algorithmic versus axiomatic definitions of matroids, pages 98 111. Springer Berlin Heidelberg, Berlin, Heidelberg, 1981.
[23] W. Hoeffding. Probability incqualities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30 1963.
[24] R. Holte, A. Mok, L. Rosier, I. Tulchinsky, and D Varvel. Pinwheel: a real-time scheduling problem. volume 2, pages 693 702 vol.2, 02 1989.
[25] T. Jacobs and S. Longo. A perspective on the windows scheduling problem. abs/1410.7237, 2014.
CoRR,
[26] Khot, R. Lipton, E. Markakis, and A. Mehta. Inapproximability results for combinatorial auctions with submodular utility functions. In Proceedings of the First International Confer- ence on Internet and Network Economics, WINE'05, page 92 101, Berlin, Heidelberg, 2005. Sprilg.r-Verlag..
[27] R. Kleinberg and N. Immorlica. Recharging bandits. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 309-319, 2018.
[28] R. Kleinberg, A. Niculescu-Mizit, and Y. Sharma. Regret bounds for sleeping experts and bandits. Mach. Learn., 80(2-3):245-272 September 2010.

---

[29] N. Korula, V. Mirrokni, and M. Zadimoghaddam. Online submodular welfare maximization: Greedy beats 1/2 random order. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, page for Computing Machinery.
New York, NY, USA, 2015. Association
[30] B. Kveton, Z. Wen, A. Ashkan, H. Eydgahi, and B. Eriksson. Matroid bandits: Fast combinato- rial optimization with learning. In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, UAI' 14, page 420-429, Arlington, Virginia, USA, 2014, AUAI Press.
[31] B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvári. Combinatorial cascading bandits. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume NIPS' 15, page 1450-1458, Cambridge, MA, USA, 2015. MIT Press.
[32] B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari. Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits In Guy Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Highteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pages 535-543, San Diego, California, USA, 09-12 May 2015. PMLR.
[33] T.L Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Adv. Appl. Math., (1)):422,, March 1985.
[34] T. Lattimore and C. Szepesvári. Bandit algorithms. preprint, page 28, 2018.
[35] R. P. Leme. Gross substitutability: An algorithmic survey. Games Econ. Behav. 106:294-316.
2017.
[36] V. Mirrokni, M. Schapira, and J. Vondrak. Tight information-theorrtie lower bounds for welfare maximization in combinatorial auctions. In Proceedings of the 9th ACM Conference on Electronic Commerce, EC '08, page 70-77, New York. NY, USA, 2008. Association for Computing Machinery.
[37] J. G. Oxley. Matroid Theory (Oxford Graduate Texts in Mathematics). Oxford University Press, Inc., New York, NY, USA, 2006.
[38] C. H. Papadimitriou and J. N. Tsitsiklis. The complexity of optimal queuing network control. Mathematics of Operations Research, 24(2):293-300 1999.
[39] C. Pike-Burke and S. Grunewalder. Recovering bandits. In Advances in Neural Information Processing Systems 32, pages 14122-14131. 2019.
[40] G. C. Robinson and D. J. A. Welsh. The computational complexity of matroid properties. Mathematical Proceedings of the Cambridge Philosophical Society. 87(1):29 45, 1980.
[41] K. A. Sankararaman and A. Slivkins. Combinatorial semi-bandits with knapsacks. In AISTATS, 2018.
[42] A. Schrijver. Combinatorial Optimization Polyhedra and Efficiency. Springer, 2003.
[43] J. Sgall, H. Shachnai, and T. Tamir. Periodic scheduling with obligatory vacations. Theoretical Computer Science, 410(47):5112 5121, 2009.
[44] A. Slivkins. Dynamic ad allocation: Bandits with budgets. ArXiv, abs/1306.0155, 2013.
[45] C. Tekin and M. Liu. Online learning of rested and restless bandits. IEEE Transactions on Information Theory, 58(8):5588-556 2012.
[46] W. R. Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-29 1933.
[47] J. Vondrak. Optimal approximation for the submodular welfare problem in the value oracle model. Proceedings of the Fortieth Annual ACM Symposium Theory of Computing, STOC '08, page 67-74, New York, NY, USA, 2008. Association for Computing Machinery.
12

---

[48] Q. Wang and W. Chen. Improving regret bounds for combinatorial semi-bandits with proba- bilistically triggered arms and its applications. Advances in Neural Information Processing Systems, pages 1161-1171 2017.
[49] P. Whittle. Restless bandits: activity allocation in changing world. Journal of Applied Probability, 25(A))287-298, 1988.
13


Reviews:
[{"review_id": "zoy67Zm8JKg", "reviewer": "Reviewer_hwtn", "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$. \n\nThere 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. \n\nThe 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.\n\nThe 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$).\n\nThe 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).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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$?\n\nThere 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "vpAlk_uWrRR", "reviewer": "Reviewer_b67u", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nTechnically, 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.\n\nMore detailed comments:\n\n- 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.\n\n- Line 101, what is $x_i$?\n\n- Line 195, Theorem 1.4. It would be better if the authors also include the gap-dependent bound in the theorem.\n\n- 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?\n\n- Line 263-264, \"For integral solutions, the above objective is equivalent to ....\" Why is this so?\n\n- Line 297, notation $\\mathcal{X}$ is not explained.\n\n- 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.\n\n- 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.\n\n- 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?\n\n- 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.\n\n========= Post rebuttal comments ===============\n\nI 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The research is a theory work, and there is no perceived negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "There is no ethical concern on this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "llnIWA9tc1R", "reviewer": "Reviewer_GPpn", "summary": "This paper focuses on matroid blocking semi-bandit and connected this problem to the problem of recurrent submodular welfare maximization.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n2) In the introduction, the author reviewed the previous works. Still, related papers like [1] have not been appropriately discussed.\n3)the author successfully addressed the issue and recommended the algorithm. \n4) The paper is well-organized and well-written.\n5) The proof is mathematically correct.\n[1]Chen, Lin, Andreas Krause, and Amin Karbasi. \"Interactive Submodular Bandit.\" Advances in Neural Information Processing Systems 30 (2017).\n\n----------- Post Rebuttal------------- \n\nI have read all the comments, and I don't change my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitations and potential negative social impact of their work.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "GEs83EFk8e7", "reviewer": "Reviewer_WQ2T", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1) Originality:\nOne 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.\n\n2) Quality:\nThis paper is technically sound. Most of the claims are supported by theoretical analysis.\n\n3) Clarity:\nThis paper is clearly written and well organized.\n\n4) Significance:\nThe 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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).\n2) 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "0phvsh3FxF3", "reviewer": "Reviewer_F9ZW", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nTechnical 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. \n\nKnown 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?\n\nSummary 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.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The broader impact section is not provided. I do not see any immediate negative impacts. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

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)