The easy version (error minimax)
Fix a depth budget $T$. The game "algorithm picks a depth-$T$ tree, adversary picks an input, payoff = probability of error" is zero-sum and finite, so von Neumann gives $$\mathrm{R}_\varepsilon(f) \;=\; \max_{\mu}\ \mathrm{D}^{\mu}_{\varepsilon}(f),$$ where $\mathrm{D}^\mu_\varepsilon(f)$ is the least depth of a deterministic tree erring with probability $\le\varepsilon$ under $\mu$. No subtleties.
The hard version (cost minimax)
Now fix the error and minimise the cost. Yao (1977) asked whether $$\bar{\mathrm{R}}_\varepsilon(f) \;\stackrel{?}{=}\; \Theta\Big(\max_\mu\ \bar{\mathrm{D}}^{\mu}_{\varepsilon}(f)\Big).$$ This is no longer a plain zero-sum game, because the error constraint is a hard constraint rather than a payoff.
- Yes for bounded error [Vereshchagin98].
- No for small bias $\varepsilon = 1/2-o(1)$ [BBGM22].
The repair
[BenDavidBlais20minimax] prove a new minimax theorem producing a single hard distribution that works at all bias levels simultaneously, and show it applies to randomized query complexity, communication complexity, approximate degree and approximate log-rank. This is the technical engine behind the $\mathrm{noisyR}$ composition theorem.