Online convex optimization in the bandit setting: gradient descent without a gradient

TLDR

Online convex optimization in the bandit setting has previously achieved \(O(\sqrt{n})\) regret when full cost functions are revealed, but only \(O(n^{3/4})\) bounds were known when only function values at chosen points are observed. The authors aim to analyze a general online convex optimization problem where only the cost at the chosen point is observed. They propose a simple gradient‑approximation scheme that evaluates the cost at a single random point each round and uses this biased estimate to drive a gradient‑descent‑style update. Using this scheme they prove an expected regret of \(O(n^{3/4})\) against an adaptive adversary, showing that gradient descent can be performed without observing full cost functions.

Abstract

We study a general online convex optimization problem. We have a convex set S and an unknown sequence of cost functions c1, c2,..., and in each period, we choose a feasible point xt in S, and learn the cost ct(xt). If the function ct is also revealed after each period then, as Zinkevich shows in [25], gradient descent can be used on these functions to get regret bounds of O(√n). That is, after n rounds, the total cost incurred will be O(√n) more than the cost of the best single feasible decision chosen with the benefit of hindsight, minx Σ ct(x).We extend this to the setting, where, in each period, only the cost ct(xt) is revealed, and bound the expected regret as O(n3/4).Our approach uses a simple approximation of the gradient that is computed from evaluating ct at a single (random) point. We show that this biased estimate is sufficient to approximate gradient descent on the sequence of functions. In other words, it is possible to use gradient descent without seeing anything more than the value of the functions at a single point. The guarantees hold even in the most general case: online against an adaptive adversary.For the online linear optimization problem [15], algorithms with low regrets in the bandit setting have recently been given against oblivious [1] and adaptive adversaries [19]. In contrast to these algorithms, which distinguish between explicit explore and exploit periods, our algorithm can be interpreted as doing a small amount of exploration in each period.