= \epsilon n$).

\[lemma:approximateCS\] Consider a scenario where $x^S$ satisfies: (i) for all $i \in [m]$, $a_i(x^S) \le B$ and (ii) for all $i \in [m]$ with $p^S_i > 0$, $a_i(x^S) \ge (1 - 3 \epsilon) B$. Then $x^S$ is good.

Moreover, since we are making decisions based on the *optimal* reduced cost for the sampled LP, our solution satisfies the above properties for the sampled LP.

\[lemma:sampleCS\] In every scenario, $x^S$ satisfies the following: (i) for all $i \in [m]$, $a_i^S(x^S) \le (1 - \epsilon)B$ and (ii) for every $i \in [m]$ with $p^S_i > 0$, $a_i^S(x^S) \ge (1 - 2\epsilon) B$.

Given that $a_i(x) = {\mathbb{E}}[a^S_i(x)]$ for all $x$, the idea is to use concentration inequalities to argue that the conditions in Lemma \[lemma:approximateCS\] hold with good probability. Although concentration of $a^S_i(x)$ for *fixed* $x$ can be achieved via Chernoff-type bounds, the quantity $a^S_i(x^S)$ has undesired correlations; obtaining an effective bound is the main technical contribution of this paper.

For a given scenario, we say that $x \in \mathcal{X}$ can be *badly learned for budget $i$* if either (i) $a_i^S(x) \le (1 - \epsilon) B$ and $a_i(x) > B$ or (ii) $a^S_i(x) \ge (1 - 2\epsilon) B$ and 