I am learning the weighted majority algorithm in "foundation of machine learning" by Mohri. But I can not understand the conclusion from the book and other reference.
It has the statement
No deterministic algorithm can achieve a regret $R_T = o(T)$ over all sequences.
How can we prove this? The book provide a scenario with two experts. But I think the statement is a general case, which can not be proved by the special case.
Meanwhile, in some reference course 1 and course 2, they said
Assume the number of mistakes the best expert makes is L ≤ T /2. Then, in the worst case, no deterministic algorithm can make fewer than 2L mistakes.
It is confused why the author also proves the general statement by using a special case. Is there any way to prove these two statements by using general cases?