We saw in the class that the Follow-the-Leader algorithm has regret (T). For that, we showed that with only two experts, an adversary can ensure a regret of at least 0.257 for the Follow-the-Leader algorithm (Slide 9 of Module 12). Recall that we assume the algorithm distributes the weights evenly between all leaders if more than one leader exists. Emma wants to extend this result to more than two experts. She assumes there are n experts e1, e2,..., en and forms the following adversarial inputs for the loss of these experts (recurring pattern emerges every n instances.) loss €1 €2 €3 €4 en-1 en t: 1 0 1 1 1 1 1 t: 2 1 0 1 1 1 1 t: 3 1 1 0 1 1 1 t: 4 1 1 1 0 t:n 1 1 1 1 0 1 t: n tn+1 1 1 1 1 1 0 1 1 1 1 0 1 Follow the steps of the Follow-the-Leader algorithm for Emma's adversarial input; specify distribution vector på at each step and write down the regret of the algorithm as a function of n and T.

We saw in the class that the Follow-the-Leader algorithm has regret (T). For that, we showed that with only two experts, an adversary can ensure a regret of at least 0.257 for the Follow-the-Leader algorithm (Slide 9 of Module 12). Recall that we assume the algorithm distributes the weights evenly between all leaders if more than one leader exists. Emma wants to extend this result to more than two experts. She assumes there are n experts e1, e2,..., en and forms the following adversarial inputs for the loss of these experts (recurring pattern emerges every n instances.) loss €1 €2 €3 €4 en-1 en t: 1 0 1 1 1 1 1 t: 2 1 0 1 1 1 1 t: 3 1 1 0 1 1 1 t: 4 1 1 1 0 t:n 1 1 1 1 0 1 t: n tn+1 1 1 1 1 1 0 1 1 1 1 0 1 Follow the steps of the Follow-the-Leader algorithm for Emma's adversarial input; specify distribution vector på at each step and write down the regret of the algorithm as a function of n and T.