First, for every normalized nonnegative utility, the comparator value
is at least the learner value. Keep the learner's representation map and,
on each fiber, choose a circuit maximizing its total utility there. That
deterministic choice dominates the stochastic mixture and belongs to the
comparator class. Thus distortion is at least one.
Put
\[
\begin {aligned}
D&=\sqrt {Nr}+\sqrt {\frac N2\log (4p)},&
B&=\sqrt {N(r+\log p)},\\
T&=\min \{\sqrt m,R_{Q,\mathfrak E,H}\},&
x&=\min \{\sqrt m,N/(2D)\}.
\end {aligned}
\]
Since \((\log 4)/2<1\leq r\) and \(\log p\geq 0\), we have
\(D\leq 2B\). Consequently \(N/(2D)\geq N/(4B)\geq R_{Q,\mathfrak E,H}/4\)
and \(x\geq T/4\). Every denominator is positive.
If \(m=1\), assign utility one to the sole circuit response at every
query. Distortion is one and \(T\leq 1\). If \(m\geq 2\) but \(x<2\), assign
the same strict normalized values \(2(m-j)/(m(m-1))\) to the circuits in
index order at every query. Distortion is at least one and \(T<8\), which
proves the claimed bound. Extend both assignments by zero to all other
responses.
In the remaining case set \(k=\lfloor x\rfloor \). Then
\[
2\leq k\leq \sqrt m,\qquad kD\leq N/2,
\qquad k\geq x/2\geq T/8.
\]
Write \([k]=\{1,\ldots ,k\}\) and fix a map \(f:Q\to [k]\)
supplied by Lemma [ftip-009C]. At a query with label \(i=f(q)\), fix the strict order
putting \(c_i\) first and the remaining circuits in increasing index order.
Let \(\operatorname {rank}_i(j)\in \{1,\ldots ,m\}\) be the position of
\(c_j\), with the first circuit at rank one, and define
\[v_i(j)=\frac {2(m-\operatorname {rank}_i(j))}{m(m-1)}.\]
These values decrease strictly in the fixed order, sum to one and
lie in \([0,2/m]\). The ordinal profile is now fixed independently of the
learner's output. Run the deterministic learner on this profile and
\(\mathfrak m_0\), obtaining \((e,h,C_0)\). Write \(h_z(j)=h(z)(c_j)\)
for the probability of circuit \(c_j\) at representation \(z\). For each \(z\in H\), choose
\(i_z\in [k]\) minimizing \(h_z(j)\) over \(j\in [k]\), breaking ties by index.
Since \(\sum _{j=1}^k h_z(j)\leq 1\), we have \(h_z(i_z)\leq1/k\).
Let \(A=\{q:f(q)=i_{e(q)}\}\) and \(S=|A|\). The lower partition
bound gives
\[
S=\sum _zX_{z,i_z}\geq \sum _z\min _{j\in [k]}X_{z,j}
\geq N/k-D\geq N/(2k).
\]
Fix \(\epsilon =1/4\). For \(i=f(q)\), assign
\[
u(q,c_j(q))=
\begin {cases}
(1-\epsilon )\mathbf 1_{j=i}+\epsilon v_i(j),&q\in A,\\
(1-\epsilon )/m+\epsilon v_i(j),&q\notin A.
\end {cases}
\]
Each row is nonnegative and sums to one. On selected queries the
added peak favors the already highest-ranked circuit; on the other
queries the same constant is added to every circuit. Hence every row
induces exactly the fixed strict order. Pointwise response separation
makes these assignments well-defined on \(Q\times Y\); assign zero to
responses outside the attained circuit responses. Because the final
utility has the unchanged ordinal profile, the deterministic learner
returns the same \((e,h,C_0)\).
Write \(W=NU\) for total utility. A selected query gives the learner
at most \((1-\epsilon )/k+2\epsilon/m\); any other query gives at most
\((1-\epsilon )/m+2\epsilon/m\). Averaging over the stochastic router yields
\[
W_{\mathcal A}
\leq (1-\epsilon )S/k+(1-\epsilon )(N-S)/m+2\epsilon N/m
\leq S/k+2N/m.
\]
Choose the deterministic comparator \(e^*=e\) and \(h^*(z)=c_{i_z}\).
It belongs to the declared class, attains utility at least
\(1-\epsilon \geq1/2\) on each selected query and nonnegative utility
elsewhere. Thus its total utility is at least \(S/2\). If learner utility
is zero the bound follows. Otherwise, using \(S\geq N/(2k)\) and
\(k^2\leq m\),
\[
\begin {aligned}
\operatorname {Dist}_u
&\geq \frac {S/2}{S/k+2N/m}
=\frac {k}{2(1+2kN/(mS))}\\
&\geq \frac {k}{2(1+4k^2/m)}
\geq \frac {k}{10}\geq \frac {T}{80}.
\end {aligned}
\]