In the case of linear rates these challenges are even more technically involved and this is related to the fact that the Natarajan-Littlestone tree has a more complicated structure than the VCL tree (for example, we need to check all the possible mappings from some given points to labels). The Gale-Stewart game that handles the case of linear rates goes as follows: the adversary presents to the learner a tuple of points \(x\) , and two (different) colorings for these points. Similarly as before, we could not use a simpler game to obtain the result. Subsequently, as in the exponential rates case, simulating this game using data becomes more complicated than in [1]}.
Proving the arbitrarily slow rates lower bound required some extra care than in the VCL tree in order to guarantee that the designed distribution is realizable.
