Algorithm (${\mathsf{SOA}}$).

The simplest setting in which learnability is captured by the Littlestone dimension is called the [*mistake-bound model*]{} [@Littlestone87online]. Let ${\mathcal{H}}\subseteq \{\pm 1\}^X$ be a fixed hypothesis class known to the learner. The learning process takes place in a sequence of trials, where the order of events in each trial $t$ is as follows:

-   the learner receives an instance $x_t\in X$,

-   the learner responses with a prediction $\hat y_t\in \{\pm 1\}$, and

-   the learner is told whether or not the response was correct.

We assume that the examples given to the learner are realizable in the following sense: For the entire sequence of trials, there is a hypothesis $h\in {\mathcal{H}}$ such that $y_t = h(x_t)$ for every instance $x_t$ and correct response $y_t$. An algorithm in this model learns ${\mathcal{H}}$ with mistake bound $M$ if for every realizable sequence of examples presented to the learner, it makes a total of at most $M$ incorrect predictions.

Littlestone showed that the minimum mistake bound achievable by any online learner is exactly ${\operatorname{Ldim}}({\mathcal{H}})$ [@Littlestone87online]. Furthermore, he described an explicit algorithm, called the [*Standard Optimal Algorithm*]{} (${\mathsf{SOA}}$), which achieves this optimal mistake bound.

[**Standard Optimal Algorithm (${\mathsf{SOA}}$)**]{}\

1.  Initialize ${\mathcal{H}}_1 