also use the following notation: for samples $S,T$, let $S\circ T$ denote the combined sample obtained by appending $T$ to the end of $S$.

Online Learning {#sec:online}
---------------

#### Littlestone Dimension.

The Littlestone dimension is a combinatorial parameter that captures mistake and regret bounds in online learning [@Littlestone87online; @Bendavid09agnostic].[^7] Its definition uses the notion of [*mistake trees*]{}. A mistake tree is a binary decision tree whose internal nodes are labeled by elements of $X$. Any root-to-leaf path in a mistake tree can be described as a sequence of examples $(x_1,y_1),...,(x_d,y_d)$, where $x_i$ is the label of the $i$’th internal node in the path, and $y_i=+1$ if the $(i+1)$’th node in the path is the right child of the $i$’th node and $y_i = -1$ otherwise. We say that a mistake tree $T$ is [*shattered* ]{}by ${\mathcal{H}}$ if for any root-to-leaf path $(x_1,y_1),...,(x_d,y_d)$ in $T$ there is an $h\in {\mathcal{H}}$ such that $h(x_i)=y_i$ for all $i\leq d$ (see Figure \[fig:shatteredtree\]). The Littlestone dimension of ${\mathcal{H}}$, denoted ${\operatorname{Ldim}}({\mathcal{H}})$, is the depth of largest complete tree that is shattered by ${\mathcal{H}}$. We say that ${\mathcal{H}}$ is a Littlestone class if it has finite Littlestone dimension.

![[]{data-label="fig:shatteredtree"}](shatteredtree.pdf)

#### Mistake Bound and the Standard Optimal 