  We study multiclass online prediction where the learner can predict using a
list of multiple labels (as opposed to just one label in the traditional
setting). We characterize learnability in this model using the $b$-ary
Littlestone dimension. This dimension is a variation of the classical
Littlestone dimension with the difference that binary mistake trees are
replaced with $(k+1)$-ary mistake trees, where $k$ is the number of labels in
the list. In the agnostic setting, we explore different scenarios depending on
whether the comparator class consists of single-labeled or multi-labeled
functions and its tradeoff with the size of the lists the algorithm uses. We
find that it is possible to achieve negative regret in some cases and provide a
complete characterization of when this is possible. As part of our work, we
adapt classical algorithms such as Littlestone's SOA and Rosenblatt's
Perceptron to predict using lists of labels. We also establish combinatorial
results for list-learnable classes, including an list online version of the
Sauer-Shelah-Perles Lemma. We state our results within the framework of pattern
classes -- a generalization of hypothesis classes which can represent adaptive
hypotheses (i.e. functions with memory), and model data-dependent assumptions
such as linear classification with margin.
