Our approach to construct the eventually correct function \(g_t\)  passes through the adversarial online learning setting. As a first step, we introduce the standard multiclass online learning game [1]} between an adversary and a learner. In this game, the adversary picks a point \(x_t \in \mathcal {X}\)  and the learner guesses its true label \(y_t \in [k]\) .
In the standard mistake bound model [2]}, [1]}, the learner's goal is to achieve a uniformly bounded number of mistakes (and this is associated with the multiclass Littlestone dimension and the Standard Optimal Algorithm). We extend this model to the case where we can guarantee a finite number of mistakes for each realizable sequence, but without an a priori bound on the number of mistakes, i.e., this number is not uniformly bounded. This is the motivation behind definition:littletree-informal. We prove that when \(\mathcal {H}\)  does not have an infinite multiclass Littlestone tree, there exists an online learning algorithm for this setting which makes finitely many mistakes. This is exactly the eventually correct function \(g_t\)  of algorithms:universal1. To be precise, the function \(g_t\)  corresponds to the winning strategy in round \(t\)  of the learning player in the above game.
