First, it was not clear to us how to prove that if the original class \(\mathcal {H}\)  does not have an infinite multiclass Littlestone tree, then each of the induced binary classes satisfies this property as well. As a result, we developed new algorithms from scratch. There were several technical challenges that we had to overcome. The straightforward extension of the Gale-Stewart games that appear in [1]}, i.e., where the adversary presents a point \(x\)  and the learner picks a label in \([k]\)  (imitating the online learning game), does not seem to work. Therefore, we propose a more involved Gale-Stewart game where the learner proposes both a point \(x\)  and two potential labels for it, and the learner has to commit to one of the two. This game allows us to obtain tight upper and lower bounds that depend on the finiteness of the multiclass Littlestone tree. Note that the function that is obtained from the winning strategy of the leaner in this game cannot be directly used to make predictions, since it takes as input two labels. Hence, our predictor, essentially, plays a tournament between all the potential labels using this function we just mentioned. In the next step of the approach, i.e., in the transition from the online setting to the statistical setting, one needs to show how to simulate this Gale-Stewart game using the data that the learner has access to. Since our Gale-Stewart game is more complex than the one in [1]}, simulating it using data becomes more challenging.
