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?