This work studies several problems in the field of online classification, a setting of online learning where the learner’s goal is to classify an online stream of instances to their correct labels.
The first part of the thesis determines the asymptotic randomized mistake bound for the problem of prediction with expert advice, a special case of online classification which was extensively studied over the years due to its usefulness and elegant nature.
The second and third parts consider the multiclass scenario, where there are more than two classes. The focus is the bandit feedback model. The second part focuses on the case of finitely many classes, improving existing bounds. The third part characterizes the cases where learning with bandit feedback is possible even when there are infinitely many classes.