Proof that multi-armed bandit optimization has exponential regret if loss function is general

Question

I was reading Robert Kelinberg's paper on Nearly Tight Bounds for the Continuum-Armed Bandit Problem There is a section where he says:

"For a d-dimensional strategy space, any multi-armed bandit algorithm must suffer regret depending exponentially on $d$ unless the cost functions are further constrained. (This is demonstrated by a simple counterexample in which the cost function is identically zero in all but one orthant of $R^d$, takes a negative value somewhere in that orthant, and does not vary over time.)"

Here $d$ is the dimension of the set of strategies (values that we can pick at each time step).

I can't really see why that is the case, that with that given cost function you get exponential regret. Can you please help me understand how the proof would go?

Answer 1

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?