approach is that the optimal solution to this problem would generalize well over an unseen task if the new task is also drawn according to the probability distribution $p$. In other words, the solution of should perform well for the problem in that we aim to solve at the test time, assuming that $f_{\rm test}$ is sampled according to $p$. In this way, we do not need any extra computation at the test time. However, in this case, the solution that we obtain would not be the best possible solution for the task that we observe at the test time, i.e., $S_{\rm test}^*$ is not equal to $S_{\rm exp}^*$. Note that we often do not have access to the underlying probability distribution $p$, and we only have access to a large set of realizations of tasks in the training phase. As a result, instead of solving , we settle for maximizing the sample average function $$\label{empirical_max}
    \max_{S\in V, |S|\leq k} \ \frac{1}{m}\sum_{i=1}^m f_i(S),$$ where $m$ is the number of available tasks in the training phase.

Problems and can be considered as two different extreme cases. In the first option, by solving , we avoid any pre-processing in the training phase, 