The problem
Consider two $d$-dimensional POVMs, $ \mathcal{E}$ and $\mathcal{F}$, given by POVM elements $\left\{E_{1}, \ldots E_{n}\right\}$ and $\left\{F_{1}, \ldots F_{n}\right\}$, respectively. (a POVM is a set of positive semi-definite Hermitian matrices $\{G_{i}\}$ on a Hilbert space $\mathcal {H}$ that sum to the identity matrix, ${\displaystyle \sum _{i=1}^{n}G_{i}=\operatorname {I} .}$)
Suppose that for some state $|\psi\rangle \in \mathbb{C}^{d} \otimes \mathbb{C}^{d}$ we have that $$ \left\langle\psi\left|\left(E_{i} \otimes F_{j}\right)\right| \psi\right\rangle \leq \epsilon $$ for all distinct $i, j \in\{1, \ldots, n\}$, where $\epsilon<1$. Upper bound, as tightly as you can, the 2-norm $$ \|\left(E_{i} \otimes I_{d}\right)|\psi\rangle-\left(I_{d} \otimes F_{i}\right)|\psi\rangle \| $$ in terms of $\epsilon$.
My attempt
For distinct $i,j$, we have $$ \label{bound} \left\langle\psi\left|\left(E_{i} \otimes F_{j}\right)\right| \psi\right\rangle \leq \epsilon. $$ As $i,j$ runs from $1$ to $n$ we have $n^2-n$ choices of distinct $i,j$. Summing them up $$ \sum^n_{i,j;i\neq j}\left\langle\psi\left|\left(E_{i} \otimes F_{j}\right)\right| \psi\right\rangle \leq \left(n^2-n\right)\epsilon. $$ Since the total probability over all choices of $i,j$ is $1$, we have the following lower bound on the total probability when $i=j$,
\begin{equation} \sum^n_i\left\langle\psi\left|\left(E_{i} \otimes F_{i}\right)\right| \psi\right\rangle\geq 1-\left(n^2-n\right)\epsilon. \end{equation}
We need to upper bound $$ \|\left(E_{i} \otimes I_{d}\right)|\psi\rangle-\left(I_{d} \otimes F_{i}\right)|\psi\rangle \| $$ Taking square, \begin{eqnarray*} \|\left(E_{i} \otimes I_{d}\right)|\psi\rangle-\left(I_{d} \otimes F_{i}\right)|\psi\rangle \|^2&=&\|\left(E_{i} \otimes I_{d}\right)|\psi\rangle\|^2-2\langle\psi|E_i\otimes F_i|\psi\rangle+\|\left(F_{i} \otimes I_{d}\right)|\psi\rangle\|^2\\ &\leq& 2-2\langle\psi|E_i\otimes F_i|\psi\rangle \end{eqnarray*} Summing over all $i$, \begin{eqnarray*} \sum^n_i\|\left(E_{i} \otimes I_{d}\right)|\psi\rangle-\left(I_{d} \otimes F_{i}\right)|\psi\rangle \|^2&\leq&2n-2\sum^n_i\langle\psi|E_i\otimes F_i|\psi\rangle \end{eqnarray*} Substituting for $\sum^n_i\left\langle\psi\left|\left(E_{i} \otimes F_{i}\right)\right| \psi\right\rangle$ from above, we get, \begin{eqnarray*} \sum^n_i\|\left(E_{i} \otimes I_{d}\right)|\psi\rangle-\left(I_{d} \otimes F_{i}\right)|\psi\rangle \|^2&\leq&2n-2 \left(1-\left(n^2-n\right)\epsilon\right)\\ &\leq&2\left(n^2-1\right)\epsilon \end{eqnarray*} Hence, we get our upper bound as, $$ \|\left(E_{i} \otimes I_{d}\right)|\psi\rangle-\left(I_{d} \otimes F_{i}\right)|\psi\rangle \|\leq \sqrt{\sum^n_i\|\left(E_{i} \otimes I_{d}\right)|\psi\rangle-\left(I_{d} \otimes F_{i}\right)|\psi\rangle \|^2}\leq\sqrt{2\left(n^2-1\right)\epsilon} $$
Is this correct? Does a better solution exist?