should directly optimize $f_{\rm{test}}$ by solving the following problem $$\label{test_problem}
    \max_{S\in V, |S|\leq k}\  f_{\rm{test}}(S).$$ We denote the optimal solution of by $S_{\rm test}^*$. For instance, we can use the greedy procedure to solve  which leads to a $(1-1/e)$-optimal solution using $\mathcal{O}(kn)$ evaluations of $f_{\rm test}$, and through $k$ passes over the ground set. However, the available computational power and time in the test phase is often limited, either because we need to make quick decisions to respond to new users or since we need to save energy. For instance, in real-world advertising or recommendation systems, both these requirements are crucial: many users arrive within each hour which means fast optimization is crucial (especially if $n,k$ are large), and also, reducing computation load would lead to huge energy savings in the long run. In such cases, Problem  should be solved approximately with less computation.

An alternative to reduce computation at test time is to solve the problem associated with the expected reward over all possible tasks in the training phase (when we have sufficient computation time), i.e., $$\label{expected_max}
    \max_{S\in V, |S|\leq k} \ \mathbb{E}_{i \sim p}\; [f_i(S)].$$ We denote the optimal solution of by $S_{\rm exp}^*$. The rationale behind this 