Let $\mathcal{Y}$ and $\mathcal{X}$ be finite sets and let $Q_Y$ be a fixed probability mass function on $\mathcal{Y}$. Also, let $P_{X | Y}$ be some fixed conditional distribution on $\mathcal{X} \times \mathcal{Y}$ and let $R$ be a positive constant.
We define
\begin{equation} A^- =\min_{Q_{U | Y}: I(U;Y) \leq R} \max_{Q_{X | Y}} \left[H(X | U) - D(Q_{X | Y} || P_{X | Y})\right], \end{equation}
where $\max_{Q_{X | Y}}$ is taken over the conditional distributions on $\mathcal{X} \times \mathcal{Y}$ and $\min_{Q_{U | Y}}$ is taken over the conditional distributions on $\mathcal{U} \times \mathcal{Y}$ with $\mathcal{U}$ being any finite set. $D$ denotes the Kullback-Leibler Divergence, $H$ is the Shannon Entropy and $I$ the mutual information. In the above expression, $I(U;Y)$ is computed with respect to $Q_YQ_{U | Y}$ and $H(X | U)$ is computed with respect to the Markov chain $Q_YQ_{U | Y}Q_{X | Y}$.
Next, we define
\begin{equation} A^+ =\min_{Q_{U | Y}: I(U;Y) \leq R} \max_{Q_{X | Y, U}} \left[H(X | U) - D(Q_{X | Y, U} || P_{X | Y})\right], \end{equation}
where $\max_{Q_{X | Y, U}}$ is taken over the conditional distributions on $\mathcal{X} \times \mathcal{Y} \times \mathcal{U}$ and $\min_{Q_{U | Y}}$ is taken over the conditional distributions on $\mathcal{U} \times \mathcal{Y}$ with $\mathcal{U}$ being any finite set. $I(U;Y)$ is computed with respect to $Q_YQ_{U | Y}$ and $H(X | U)$ is computed with respect to $Q_YQ_{U | Y}Q_{X | Y, U}$ (i.e., no longer with respect to a Markov chain).
Numerical evidence appears to suggest that
\begin{equation} A^+ = A^-. \end{equation}
I appreciate any ideas on how one might go about proving or disproving the (implied) conjecture. Observe that while in $A^+$ we have more freedom in tuning $H(X | U)$, we potentially pay for this freedom as $D(Q_{X | Y, U} || P_{X | Y}) \geq D(Q_{X | Y} || P_{X | Y})$ with equality iff $Q_{X | Y, U} = Q_{X | Y}$.
