of infinite size. Each task $\mathcal{T}_i$ is represented via a set function $f_i:2^{V} \to {\mathbb{R}}_+$ that measures the reward of a set $S \subseteq V $ for the $i$-th task, and performing the task $\mathcal{T}_i$ would mean to maximize the function $f_i$ subject to a given constraint. For instance, in a recommender system where we aim to recommend a subset of the items to the users, the set $\mathcal{I}$ denotes the set of all the possible users and selecting which items to recommend to a user $i \in \mathcal{I}$ is viewed as the task $\mathcal{T}_i$. Moreover, the function $f_i$ encodes the users satisfaction, i.e., $f_i(S)$ quantifies how suitable the set of items $S$ is for user $i$. Taking a statistical perspective, we assume that the tasks $\mathcal{T}_i$ occur according to a possibly unknown probability distribution $i \sim p$.

In this paper, we focus on the case where the functions $f_i$ are monotone and submodular set functions and each task $\mathcal{T}_i$ amounts to maximizing $f_i$ under the $k$-cardinality constraint. That is, the task $\mathcal{T}_i$ is to select a subset $S \subseteq V$ of size $k$ such that the value of $f_i(S)$ is maximized. Submodularity of $f_i$ means that for any $A,B 