We study a general online convex optimization problem. We have a convex set S and an unknown sequence of cost functions ct, c2,..., and in each period, we choose a feasible point xt in S, and learn the cost ct(xt). If the fimction 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(~/~). That is, after n rounds, the total cost incurred will be O(v/~ ) more than the cost of the best single feasible decision chosen with the benefit of hindsight, min~ ~ ct (x). We extend this to the "bandit" setting, where, in each period, only the cost ct(xt) is revealed, and bound the expected regret as O(na/4). Our approach uses a simple approximation of the gradient that is computed fl'om evaluating ct at a single (random) point. We show that this biased estimate is sufficient to ap-3. proximate gradient descent on the sequence of flmctions. 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.
In particular, REF proposed to use a simple trick to approximate the gradient of a function with a single data sample.
Online convex optimization in the bandit setting: gradient descent without a gradient
SODA '05
Mathematics Computer Science