A lower bound for the regret of aggregating expert advice algorithms for a changing number of active experts

This paper considers the setting of online learning with expert advice with the set of experts growing on each trial. The total loss incurred by the Predictor is compared with the loss of the best compound expert, that is the sequence of experts chosen off-line by partitioning the training sequence into several sections and then choosing the best expert for each section. We propose lower bounds on the regret of any algorithm that solves this problem. The lower bounds have the same asymptotic growth rate as the known upper bounds.