Minimax Regret for Bandit Convex Optimisation of Ridge Functions

We analyse adversarial bandit convex optimisation with an adversary that is restricted to playing functions of the form ft(x) = gt(langle x, θrangle) for convex gt : mathbb R → mathbb R and unknown θ ∈ mathbb Rd that is homogeneous over time. We provide a short information-theoretic proof that the minimax regret is at most O(d √n log(n operatornamediam(mathcal K))) where n is the number of interactions, d the dimension and operatornamediam(mathcal K) is the diameter of the constraint set.