This obviously depends on the "closeness" measure of the lower bound. FWIW, for any $n$ (let $n = 2k$ even for simplicity) and the following input values:

• $\alpha_1 = \alpha_k = 0$, $\alpha_{k + 1} = \alpha_{2k} = 1$,
• $v_1 = v_2 = \ldots = v_{2k} = 1$,
• $p(1) = \ldots = p(2k) = \frac{1}{k + 1}$,

$\mathbb{E}(X)$ can be both:

• $\frac{1}{k + 1}$, when $S_1, \ldots, S_{k + 1}$ are equiprobable, and $S_1, \ldots, S_k$ are singleton sets $\{1\}, \ldots, \{k\}$, $S_{k + 1} = \{k + 1, \ldots, 2k\}$,
• $1 - \frac{1}{k + 1}$, for a symmetrical construction.

Thus, $\mathbb{E}(X)$ can't be approximated from below within factor $O(n)$, or $1 - \Omega(1 / n)$ absolute error.

This obviously depends on the "closeness" measure of the lower bound. FWIW, for any $n$ (let $n = 2k$ even for simplicity) and the following input values:

• $\alpha_1 = \alpha_k = 0$, $\alpha_{k + 1} = \alpha_{2k} = 1$,
• $v_1 = v_2 = \ldots = v_{2k} = 1$,
• $p(1) = \ldots = p(2k) = \frac{1}{k + 1}$,

$\mathbb{E}(X)$ can be both:

• $\frac{1}{k + 1}$, when $S_1, \ldots, S_{k + 1}$ are equiprobable, and $S_1, \ldots, S_k$ are singleton sets $\{1\}, \ldots, \{k\}$, $S_{k + 1} = \{k + 1, \ldots, 2k\}$,
• $1 - \frac{1}{k + 1}$, for a symmetrical construction.

Thus, any lower bound on $\mathbb{E}(X)$ would have worst-case $\Omega(n)$ relative error, or $1 - O(1 / n)$ absolute error.