\section{Proofs for Sections~\ref{sec:prelim} and~\ref{sec:bayes}}\label{app:bayes}

The proofs are hierarchical in the style of Lamport~\cite{Lam95}: each step is a claim with its own proof,
and \textsc{q.e.d.} marks the step that concludes its level.

\subsection{The Bayes decision rule}

\lembayesrule*

\begin{proof}[Proof of \cref{lem:bayesrule}]
\begin{steps}
\step{1}{1} Condition on the inputs $x_1,\dots,x_{m+1}$ and the labels $y_1,\dots,y_m$. Then the task has
distribution $\pi_S$, and $\Pr[y_{m+1}=1\mid S,x_{m+1}]=\hat p_S(x_{m+1})$.
\pf The inputs are independent of the task and of the noise. Given the inputs, the probability of the labels
$y_1,\dots,y_m$ under task $w$ is $\prod_{i\le m}\eta^{[h_w(x_i)\ne y_i]}(1-\eta)^{[h_w(x_i)=y_i]}
=(1-\eta)^m\mu^{e_S(w)}$, and the prior is uniform, so the posterior is proportional to $\omega_S(w)$. The
target is $h_w(x_{m+1})\oplus\xi_{m+1}$ with $\xi_{m+1}$ independent of everything else, so it is $1$ with
probability $\sum_w\pi_S(w)\,[(1-\eta)h_w(x_{m+1})+\eta(1-h_w(x_{m+1}))]=\hat p_S(x_{m+1})$.

\step{1}{2} For every in-context learner $A$, the conditional error probability given $S$ and $x_{m+1}$ is at least
$\min\{\hat p,1-\hat p\}$, with $\hat p=\hat p_S(x_{m+1})$, and $\Bayes$ attains it.
\pf Given $S$ and $x_{m+1}$, the output of $A$ depends only on its own random bits, which are independent of
the target. If $A$ outputs $1$ with conditional probability $q$, it errs with probability
$q(1-\hat p)+(1-q)\hat p\ge\min\{\hat p,1-\hat p\}$. Since $\hat p-1/2=(1-2\eta)(p_S(x_{m+1})-1/2)$ and
$\eta<1/2$, the predictor $\Bayes$ outputs $1$ exactly when $\hat p\ge1/2$, so its conditional error is
$\min\{\hat p,1-\hat p\}$.

\qedstep{1}{3}
\pf Take expectations in \sref{1}{2}.
\end{steps}
\end{proof}

\subsection{Algorithms}

\thmbayesalg*

\begin{proof}[Proof of \cref{thm:bayesalg}]
\begin{steps}
\step{1}{1} \Let $S^+$ be $S$ followed by the example $(x,1)$. Then
$\omega_{S^+}(w)=\omega_S(w)\,\mu^{[h_w(x)\ne1]}$ for every $w$.
\pf The error count of $w$ on $S^+$ is $e_S(w)+[h_w(x)\ne1]$.

\step{1}{2} Part~\ref{it:noiseless} holds.
\begin{steps}
\step{2}{1} $p_S(x)=|\VS(S^+)|/|\VS(S)|$.
\pf For $\eta=0$ the posterior is uniform on $\VS(S)$, and the descriptions in $\VS(S)$ with $h_w(x)=1$ are
exactly those in $\VS(S^+)$.
\step{2}{2} $p_S(x)$ and $\Bayes(S,x)$ can be computed in time $\poly(N,m)\cdot2^\kappa\cdot T_\kappa(N)$.
\pf \Cref{fact:vs} computes both counts, for samples of sizes $m$ and $m+1$. Both are integers below
$2^{N+1}$, so the quotient and its comparison with $1/2$ take polynomial time.
\step{2}{3} The Gibbs predictor runs exactly in the same time.
\pf \Cref{fact:vs} draws a uniform element $w$ of $\VS(S)$, which is a draw from $\pi_S$, and $h_w(x)$ is
computable in polynomial time.
\step{2}{4} If $\kappa=o((\log N)^{1/4}/\sqrt{\log\log N})$, the time is $\poly(m)\cdot2^{o(N)}$.
\pf Then $\kappa^2g(N)=\kappa^2N\log\log N/\sqrt{\log N}=o(N)$ and $2^\kappa=2^{o(N)}$, and
$\poly(N)=2^{o(N)}$.
\qedstep{2}{5}
\end{steps}

\step{1}{3} Part~\ref{it:noisy} holds.
\begin{steps}
\step{2}{1} \Let, for $j\in\{0,\dots,m\}$, $a_j$ and $b_j$ be the numbers of descriptions $w$ with $e_S(w)=j$ and
$h_w(x)=1$, respectively $h_w(x)=0$, and \Let $b_{-1}=a_{m+1}=0$. \Let $c_j$ and $c^+_j$ be the coefficients
of $V^j$ in $E_S$ and $E_{S^+}$. Then $c_j=a_j+b_j$ for $0\le j\le m$ and $c^+_j=a_j+b_{j-1}$ for $0\le j\le
m+1$.
\pf By \sref{1}{1} with $V$ in place of $\mu$: a description with $h_w(x)=1$ contributes $V^{e_S(w)}$ to
$E_{S^+}$, and one with $h_w(x)=0$ contributes $V^{e_S(w)+1}$.
\step{2}{2} The numbers $a_j,b_j$ for $0\le j\le m$ are determined by the coefficients: $a_j=c^+_j-b_{j-1}$ and
$b_j=c_j-a_j$, in the order $j=0,1,\dots,m$.
\pf By \sref{2}{1} and induction on $j$, starting from $b_{-1}=0$.
\step{2}{3} $p_S(x)=\sum_{j=0}^ma_j\mu^j\big/\sum_{j=0}^mc_j\mu^j$, and the denominator is positive.
\pf $\sum_{w:h_w(x)=1}\omega_S(w)=\sum_ja_j\mu^j$ and $Z_S=\sum_jc_j\mu^j$. Since $\mu>0$ and
$\sum_jc_j=2^N$, $Z_S>0$.
\step{2}{4} $p_S(x)$ and $\Bayes(S,x)$ can be computed in time $\poly(N,m,\log b)\cdot2^{O(s/\sqrt{\log s})}$.
\pf \Cref{fact:profile} computes $E_S$ and $E_{S^+}$; the parameter of the second is $s$, and that of the
first is at most $s$. With $\mu=a/(b-a)$, multiplying numerator and denominator by $(b-a)^m$ turns them into
the integers $\sum_ja_ja^j(b-a)^{m-j}$ and $\sum_jc_ja^j(b-a)^{m-j}$, which have $O(N+m\log b)$ bits, since
$a_j,c_j\le2^N$. Computing them, the quotient and its comparison with $1/2$ takes time $\poly(N,m,\log b)$.
\step{2}{5} The Gibbs predictor runs in time $\poly(N,m,\log b)\cdot2^{O(s/\sqrt{\log s})}$, exactly given exact
samples from explicitly given distributions on $\{0,\dots,m\}$, and otherwise within statistical distance $\nu$.
\pf Apply \cref{fact:expmech} with $\lambda=\ln(1/\mu)>0$. It samples $w$ with probability proportional to
$e^{-\lambda e_S(w)}=\mu^{e_S(w)}=\omega_S(w)$, that is, from $\pi_S$; output $h_w(x)$. The distributions on
$\{0,\dots,m\}$ that it samples from have weights $c_j\mu^j$, or, after scaling by $(b-a)^m$, the integers
$c_ja^j(b-a)^{m-j}$ with $O(N+m\log b)$ bits, and computing them adds a factor $\poly(N,m,\log b)$.
\step{2}{6} If $m\ge\max\{\kappa,2\}$ then $s/\sqrt{\log s}\le8\kappa m/\sqrt{\log m}$.
\pf Here $4\kappa(m+1)\le8\kappa m$, $m+2\le2m\le8\kappa m$ and $\kappa^2\le\kappa m$, so $s\le8\kappa m$, and
$s\ge m$ gives $\log s\ge\log m$.
\qedstep{2}{7}
\end{steps}

\qedstep{1}{4}
\end{steps}
\end{proof}

\corfromcount*

\begin{proof}[Proof of \cref{cor:fromcount}]
\begin{steps}
\step{1}{1} $|\VS(S)|$ and $|\VS(S^+)|$ are the numbers of satisfying assignments of $\kappa$-CNFs $\Gamma_S$
and $\Gamma_{S^+}$ on $N$ variables with at most $(m+1)2^\kappa$ clauses each, computable in time
$\poly(N,m)\cdot2^\kappa$.
\pf \Cref{fact:vscnf} for the samples $S$ and $S^+$.
\qedstep{1}{2}
\pf Count both with the assumed algorithm, in time $T(N,(m+1)2^\kappa)$ each because $T$ is nondecreasing,
and output the quotient, which is $p_S(x)$ by \sref{2}{1} of the proof of \cref{thm:bayesalg}.
\end{steps}
\end{proof}

\subsection{The Bayes risk}

\thmrisk*

\begin{proof}[Proof of \cref{thm:risk}]
\begin{steps}
\step{1}{1} \Let an infinite episode draw $w$ uniformly, inputs $x_1,x_2,\dots$ independently from $\cD$ and
noise bits $\xi_1,\xi_2,\dots$, with $y_t=h_w(x_t)\oplus\xi_t$, and \Let $S_t$ be its first $t$ examples. Let
$(x,y)$ be one more example of the same task, independent of the sequence given $w$. Then
$R^*_t=\Pr[\Bayes(S_t,x_{t+1})\ne y_{t+1}]=\Pr[\Bayes(S_t,x)\ne y]$ for every $t\ge0$.
\pf $(w,S_t,x_{t+1},y_{t+1})$ and $(w,S_t,x,y)$ both have the distribution of an episode of length $t$ with
its task.

\step{1}{2} Part~\ref{it:mono} holds.
\begin{steps}
\step{2}{1} \Let $q_t=\Pr[y=1\mid S_t,x]$. Then $q_t=\hat p_{S_t}(x)$ and $R^*_t=\mathbb E[\min\{q_t,1-q_t\}]$.
\pf By \sref{1}{1} and \cref{lem:bayesrule}.
\step{2}{2} $\mathbb E[q_{t+1}\mid S_t,x]=q_t$.
\pf The tower property, since $(S_t,x)$ is a function of $(S_{t+1},x)$.
\step{2}{3} $\mathbb E[\min\{q_{t+1},1-q_{t+1}\}\mid S_t,x]\le\min\{q_t,1-q_t\}$.
\pf The function $q\mapsto\min\{q,1-q\}$ is concave; apply the conditional Jensen inequality and \sref{2}{2}.
\qedstep{2}{4}
\pf Take expectations in \sref{2}{3} and use \sref{2}{1}.
\end{steps}

\step{1}{3} Without noise, in every infinite episode the predictions $\hat y_t=\Bayes(S_{t-1},x_t)$ are wrong
for at most $N$ indices $t\ge1$.
\begin{steps}
\step{2}{1} $|\VS(S_0)|=2^N$, $\VS(S_t)\subseteq\VS(S_{t-1})$, and $w\in\VS(S_t)$ for all $t$.
\pf Without noise every label is $h_w(x_t)$.
\step{2}{2} If $\hat y_t\ne y_t$, then $|\VS(S_t)|\le|\VS(S_{t-1})|/2$.
\pf Let $p=p_{S_{t-1}}(x_t)$, the fraction of $\VS(S_{t-1})$ that labels $x_t$ positive. If $y_t=1$ and
$\hat y_t=0$, then $p<1/2$ and $|\VS(S_t)|=p\,|\VS(S_{t-1})|$. If $y_t=0$ and $\hat y_t=1$, then $p\ge1/2$ and
$|\VS(S_t)|=(1-p)|\VS(S_{t-1})|$.
\qedstep{2}{3}
\pf After $r$ mistakes, $1\le|\VS(S_t)|\le2^{N-r}$ by \sref{2}{1} and \sref{2}{2}, so $r\le N$.
\end{steps}

\step{1}{4} With noise rate $\eta>0$, $\sum_{t=1}^{m+1}(R^*_{t-1}-\eta)\le(1-2\eta)N/(1-\Hb(\eta))$.
\begin{steps}
\step{2}{1} \Let $P_v(y_{1..T})=\prod_{t\le T}(1-\eta)^{[y_t=h_v(x_t)]}\eta^{[y_t\ne h_v(x_t)]}$ for each
description $v$, given the inputs, and $Q=2^{-N}\sum_vP_v$. Then $Q(y_{1..t})/Q(y_{1..t-1})$ is $\hat p_t$ if
$y_t=1$ and $1-\hat p_t$ if $y_t=0$, where $\hat p_t=\hat p_{S_{t-1}}(x_t)$.
\pf $Q(y_{1..t})/Q(y_{1..t-1})$ is the conditional probability of $y_t$ given the inputs and $y_{1..t-1}$ in
the mixture, which is the predictive probability of \sref{1}{1} of the proof of \cref{lem:bayesrule}.
\step{2}{2} $\sum_{t=1}^{m+1}\log\frac{P_w(y_t\mid x_t)}{Q(y_t\mid S_{t-1},x_t)}\le N$ in every episode, where
$P_w(y_t\mid x_t)$ is the $t$-th factor of $P_w$ and $Q(y_t\mid S_{t-1},x_t)$ is the quotient of \sref{2}{1}.
\pf The sum telescopes to $\log(P_w(y_{1..m+1})/Q(y_{1..m+1}))$, and $Q\ge2^{-N}P_w$.
\step{2}{3} \Let $q_t=(1-\eta)h_w(x_t)+\eta(1-h_w(x_t))$ and
$\KL_t=\KL(\Bern(q_t)\,\|\,\Bern(\hat p_t))$ in bits. Then $\sum_{t=1}^{m+1}\mathbb E[\KL_t]\le N$.
\pf Given $w$, all inputs and $y_{1..t-1}$, the label $y_t$ is $1$ with probability $q_t$, so the conditional
expectation of the $t$-th term of \sref{2}{2} is $\KL_t$. All terms are finite because $\hat p_t\in[\eta,1-\eta]$.
\step{2}{4} If $\hat y_t\ne h_w(x_t)$, then $\KL_t\ge1-\Hb(\eta)$.
\pf For fixed $q$, the divergence $\KL(\Bern(q)\|\Bern(p))$ decreases in $p$ on $(0,q]$ and increases
on $[q,1)$. At $p=1/2$ it equals $1-\Hb(q)$, and $\Hb(q)=\Hb(\eta)$ for $q\in\{\eta,1-\eta\}$. If $h_w(x_t)=1$
and $\hat y_t=0$, then
$q_t=1-\eta>1/2>\hat p_t$. If $h_w(x_t)=0$ and $\hat y_t=1$, then $q_t=\eta<1/2\le\hat p_t$. In both cases
$1/2$ lies between $q_t$ and $\hat p_t$.
\step{2}{5} $\Pr[\hat y_t\ne y_t]=\eta+(1-2\eta)\Pr[\hat y_t\ne h_w(x_t)]$.
\pf Given $w$, $S_{t-1}$ and $x_t$, the noise bit $\xi_t$ is independent and $\hat y_t$ is fixed; the prediction
is wrong with probability $\eta$ if $\hat y_t=h_w(x_t)$ and $1-\eta$ otherwise.
\qedstep{2}{6}
\pf By \sref{1}{1}, $R^*_{t-1}=\Pr[\hat y_t\ne y_t]$. By \sref{2}{5} and \sref{2}{4},
$R^*_{t-1}-\eta\le(1-2\eta)\mathbb E[\KL_t]/(1-\Hb(\eta))$; sum and use \sref{2}{3}.
\end{steps}

\step{1}{5} Part~\ref{it:bound} holds.
\pf Without noise, \sref{1}{3} and \sref{1}{1} give $\sum_{t=1}^{m+1}R^*_{t-1}\le N$, which is the case $\eta=0$
of the inequality of \sref{1}{4}. In both cases, part~\ref{it:mono} gives $R^*_m\le R^*_{t-1}$ for $t\le m+1$,
so $(m+1)(R^*_m-\eta)\le(1-2\eta)N/(1-\Hb(\eta))$.

\step{1}{6} Part~\ref{it:gibbs} holds.
\pf Without noise, let $p=p_S(x)$ for the context $S$ and query $x$ of an episode. Given $S$ and $x$, the task
and the description drawn by $\Gibbs$ are independent draws from $\pi_S$, so $\Gibbs$ errs with probability
$2p(1-p)\le2\min\{p,1-p\}$, and $\Bayes$ errs with probability $\min\{p,1-p\}$ by \cref{lem:bayesrule}. Take
expectations and use part~\ref{it:bound}.

\qedstep{1}{7}
\end{steps}
\end{proof}