Proof that multi-armed bandit optimization has exponential regret if loss function is general
I'm not exactly sure what he means, but here's a very similar example in a discrete version. Imagine the strategy space weren't continuous but instead consisted of all points in $\{\pm 1\}^d$, one point in each of the $2^d$ orthants. The cost function $C$ is $0$ in all but one of those locations, where it is $-10$.

In order to get any decent regret, you have to figure out which point is the one with cost $-10$ and start choosing it repeatedly. But how will you figure it out? Your only way is to just try different points until you find the right one. But it will take on the order of $2^d$ tries to find it since that are the number of options.

This raises the question - how can a restriction like making $C$ convex rule out this kind of example?