Follow The Leader

This is an algorithm for Prediction with expert advice. It leads to some other algorithms, like Follow the Perturbed Leader, which are sometimes more effective. This algorithm simply follow the best expert "so far". The prediction ⚠ $\gamma^T = \arg\min \sum_{t=1}^T \lambda(\omega^t,\gamma^t_k), k=1,\ldots,K$ (see notation of Prediction with expert advice), or if there are many of them, chooses one arbitrarily.

It is clear, that it is impossible to prove good regret bounds for this algorithm even in case of a square-loss function. Indeed, assume the case of two possible outcomes ⚠ $\{0,1\}$, and two possible experts. One expert always predicts ⚠ $0$, the second one always predicts ⚠ $1$. At the first step Learner chooses to follow the first expert, so his prediction is ⚠ $0$. The reality always announces an outcome in the contrary of Leaner's prediction: this time outcome is ⚠ $1$. Then Learner suffers loss ⚠ $1$, first expert suffers loss ⚠ $1$, second expert suffers loss ⚠ $0$. At the second step Learner chooses the second expert, so his prediction is ⚠ $1$. The reality announces ⚠ $0$, so Learner again suffers loss ⚠ $1$. This way, at a time step ⚠ $T$, the loss of the Learner is ⚠ $T$, and the losses of experts are about ⚠ $T/2$ (only approximately, because when losses of experts are equal, we do not know which one suffers nonzero loss before the Learner chooses his decision). So the regret is of order ⚠ $T/2$.