= {\mathcal{H}}$.

2.  For trials $t = 1, 2, \dots$:

    -   For each $b \in \{\pm 1\}$ and $x \in X$, let ${\mathcal{H}}_t^b(x) = \{h \in {\mathcal{H}}_t : h(x) = b\}$. Define $h : X \to \{\pm 1\}$ by $h_t(x) = {\operatorname{argmax}}_b {\operatorname{Ldim}}({\mathcal{H}}_t^{b}(x))$.

    -   Receive instance $x_t$.

    -   Predict $\hat{y}_t = h_t(x_t)$.

    -   Receive correct response $y_t$.

    -   Update ${\mathcal{H}}_{t+1} = {\mathcal{H}}_t^{y_t}(x_t)$.

#### Extending the ${\mathsf{SOA}}$ to non-realizable sequences.

Our globally-stable learner for Littlestone classes will make use of an optimal online learner in the mistake bound model. For concreteness, we pick the ${\mathsf{SOA}}$ (any other optimal algorithm will also work). It will be convenient to extend the ${\mathsf{SOA}}$ to sequences which are not necessarily realizable by a hypothesis in ${\mathcal{H}}$. We will use the following simple extension of the ${\mathsf{SOA}}$ to non-realizable samples:

\[def:soaext\] Consider a run of the ${\mathsf{SOA}}$ on examples $(x_1,y_1),\ldots, (x_m,y_m)$, and let $h_t$ denote the predictor used by the ${\mathsf{SOA}}$ after seeing the first $t$ examples (i.e., $h_t$ is the rule used by the ${\mathsf{SOA}}$ to predict in the $(t+1)$’st trial). Then, after observing both $x_{t+1},y_{t+1}$ do the following:

-   If the sequence $(x_1,y_1),\ldots, (x_{t+1},y_{t+1})$ is realizable by some $h\in{\mathcal{H}}$ then apply the usual update 