# Lower Bound on Zero-order Regret

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.

• Your question would be more useful and a meaningful answer more likely if you would define the terms appearing in the question. Many readers will not know immediately what zero-order regret means. – Jan Johannsen Dec 13 '13 at 9:47