Here is a brief summary of the experts framework: Given $n$ experts who either give correct or wrong advice for each round $t\in [T]$, an algorithm is required to give a best prediction for each round based on the advice from experts.
We define the difference of total loss (either 0 or 1 for each round) incurred and that of the best expert as regret. We call the regret as a function of $n$ and $T$ the zero-order regret, as a function of $L^*$ (loss of the best expert) the first-order expert, and so on.
The upper bound on the zero-order regret is known as $O(\sqrt{T\ln n})$. I was wondering if there is also a positive lower bound on this?
I guess this is true, since I could find it in Exercise 5 in the survey Learning, Regret minimization, and Equilibria by A. Blum and Y. Mansour. I would appreciate it if anyone can give me a pointer to the proof. Thanks.
