Online Learning with an Almost Perfect Expert

We study the online learning problem where a forecaster is trying to predict each day the next bit in a sequence, such as whether the stock market will go up or down. Every morning, for T days, he solicits the opinions of a number n of experts, who each make up or down predictions. Based on their predictions, the forecaster makes a choice between up and down, then buys or sells accordingly. The goal of the forecaster is to make as few mistakes as possible given that the bit sequence may be generated adversarially. This is a classical learning problem that has been studied in a large body of literature starting with the development of Blackwell approachability [Bla56] and Hannan consistency [Han57], and continued in learning theory under the paradigm of combining expert advice [LW94, Vov90]. One of the best known approaches is the Weighted-Majority algorithm [LW94], which keeps track of weights for all the experts and changes them in every round depending on the quality of their predictions. The average number of mistakes made by the forecaster when using such an algorithm can be bounded by the number of mistakes made by the best expert plus log n/T.