Impossibility of QRAC with random question, or more general proof of impossibility

TL;DR: Is it known that QRAC where the "question" is random instead of chosen are impossible? More generally what are the methods to prove impossibility games?

I often face problems for which I want to prove that they are not solvable. Either with probability 1 (like here), but more generally I'm interested on how to find some upper bound (optimal if possible) of these problems.

As an example, let's consider the following game: I prepare a $$|+_\theta \rangle$$ with $$\theta$$ a multiple of $$\frac{\pi}{2}$$, and the goal is to output $$D \in S$$, with $$S = \{\{0,\frac{\pi}{2}\},\{0,\frac{3\pi}{2}\},\{\pi,\frac{\pi}{2}\},\{\pi,\frac{3\pi}{2}\} \}$$, such that $$\theta \in D$$.

I'd like now to see the different methods to prove that it's not possible to win this game with probability 1, or, even better, I'd like to find an upper bound, or, even better, prove the optimality.

So far, I have two methods, but they are not really perfect:

• the first method is to write a semi-definite program (SDP), where we write each possible output as a 2x2 POVM $$\{E_0, E_1, E_2, E_3\}$$, and then we solve agains the constraint that the $$E_i$$ are positive, sum to 1, and we try to maximize the success probability (which is basically a sum of projections on these POVM). Feeding that into a SDP solver program, we can prove that the optimal probability of success is about $$0.85$$. The advantage of this method is that if the SDP program is nice, we have optimal bound. The problem is that we need to trust a computer.
• another method would be, again, to write the above POVM, and manually try to find some contradiction if the probability of success is equal to 1. The advantage is that we have a proof "on the paper". The problem here is that it can be a bit tedious and long to write, and harder to "automatize", and it does not prove optimal bounds, just upper bound, or maybe simply impossibility.

Then, I tried to look at the Holevo bound, but it seems that I can't find anything interesting, because from $$D$$ I can extract at most one bit about $$\theta$$.

Talking about bounds, I was thinking also to use the Nayak's bound. Unfortunately, this game does not really encode a traditional QRAC (or it's not obvious to me), but it does encode a QRAC where the question asked by Bob is random. Indeed, if we encode a two bit string $$m$$ such that $$00$$ is encoded with $$|+_0\rangle$$, $$01$$ with $$|+_{\pi/2}\rangle$$, $$11$$ with $$|+_{\pi}\rangle$$ and $$10$$ with $$|+_{3\pi/2}\rangle$$, then if we know $$D$$ we can know for sure one bit of $$m$$, but we cannot say in advance "give me the $$n$$'th bit.

So here is my question:

1) is it known that "randomized" QRAC are impossible? 2) is there some other bound that could be useful to prove imposibility results?

Thanks!