papers/hanzo-aso/sections/13-proof-of-theorem-ref-thm-rate.tex

\section{Proof of Theorem~\ref{thm:rate}
 (Full)}
\label{app:proof-rate}

\begin{proof}
Fix token position $t$ and let $v^*$ denote the Bayes-optimal token. For each
prior $m$, define the log-odds contribution:
\begin{equation}
    X_m = \eta_m \left[\log \phi_m(v^* \mid x, y_{<t}) - \log \phi_m(v \mid x, y_{<t})\right]
\end{equation}
for any $v \neq v^*$. By construction, $X_m \geq 0$ when $\phi_m$ correctly
assigns higher probability to $v^*$ (which happens with probability $q_m$) and
$|X_m| \leq \eta_m \cdot \max_v |\log \phi_m(v)| \leq C$ for some constant $C$
determined by the maximum magnitude of the expert factors.

The total log-odds advantage for $v^*$ over $v$ after $M$ priors is:
\begin{equation}
    L_M(v^*, v) = \ell_{t,v^*} - \ell_{t,v} + \sum_{m=1}^M X_m.
\end{equation}

By assumption, $\mathbb{E}[X_m] \geq 2\delta^2$ (from $q_m > 0.5 + \delta$
and the log-odds formula). By Hoeffding's inequality:
\begin{equation}
    P\left(\sum_{m=1}^M X_m < M\delta^2\right)
    \leq \exp\left(-\frac{M\delta^2}{2C^2}\right)
    \leq \exp\left(-\frac{M\delta^2}{2}\right)
\end{equation}
for $C = 1$ (which holds when expert factors are bounded by 1 in absolute
value). Taking a union bound over all $V - 1$ incorrect tokens and noting
that the KL divergence is zero when $\pi_{\text{ASO}}(v^*) = 1$:
\begin{equation}
    P\left(\KL(\pi^* \| \pi_{\text{ASO}}^{(M)}) > \varepsilon\right)
    \leq (V-1) \exp\left(-\frac{M\delta^2}{2}\right)
    < 2V \exp\left(-\frac{M\delta^2}{2}\right).
\end{equation}
\end{proof}