This paper addresses the problem of minimizing a convex, Lipschitz function @math over a convex, compact set @math under a stochastic bandit feedback model. In this model, the algorithm is allowed to observe noisy realizations of the function value @math at any query point @math . The quantity of interest is the regret of the algorithm, which is the sum of the function values at algorithm's query points minus the optimal function value. We demonstrate a generalization of the ellipsoid algorithm that incurs @math regret. Since any algorithm has regret at least @math on this problem, our algorithm is optimal in terms of the scaling with @math .
The case of convex, Lipschitz cost functions has been looked at in the harder adversarial model @cite_9 @cite_14 by constructing one-point gradient estimators. However, the best-known regret bounds for these algorithms are @math . @cite_1 show a regret bound of @math in the adversarial setup, when two evaluations of the same function are allowed, instead of just one. However, this does not include the stochastic bandit optimization setting since each function evaluation in the stochastic case is corrupted with independent noise, violating the critical requirement of a bounded gradient estimator that their algorithm exploits. Indeed, applying their result in our setup yields a regret bound of @math .
@cite_9 @cite_14 @cite_1
2952840318 2097487180 153281708
We consider a the general online convex optimization framework introduced by Zinkevich. In this setting, there is a sequence of convex functions. Each period, we must choose a signle point (from some feasible set) and pay a cost equal to the value of the next function on our chosen point. Zinkevich shows that, if the each function is revealed after the choice is made, then one can achieve vanishingly small regret relative the best single decision chosen in hindsight. We extend this to the bandit setting where we do not find out the entire functions but rather just their value at our chosen point. We show how to get vanishingly small regret in this setting. Our approach uses a simple approximation of the gradient that is computed from evaluating a function at a single (random) point. We show that this estimate is sufficient to mimic Zinkevich's gradient descent online analysis, with access to the gradient (only being able to evaluate the function at a single point). In the multi-armed bandit problem, an online algorithm must choose from a set of strategies in a sequence of n trials so as to minimize the total cost of the chosen strategies. While nearly tight upper and lower bounds are known in the case when the strategy set is finite, much less is known when there is an infinite strategy set. Here we consider the case when the set of strategies is a subset of ℝd, and the cost functions are continuous. In the d = 1 case, we improve on the best-known upper and lower bounds, closing the gap to a sublogarithmic factor. We also consider the case where d > 1 and the cost functions are convex, adapting a recent online convex optimization algorithm of Zinkevich to the sparser feedback model of the multi-armed bandit problem. Bandit convex optimization is a special case of online convex optimization with partial information. In this setting, a player attempts to minimize a sequence of adversarially generated convex loss functions, while only observing the value of each function at a single point. In some cases, the minimax regret of these problems is known to be strictly worse than the minimax regret in the corresponding full information setting. We introduce the multi-point bandit setting, in which the player can query each loss function at multiple points. When the player is allowed to query each function at two points, we prove regret bounds that closely resemble bounds for the full information case. This suggests that knowing the value of each loss function at two points is almost as useful as knowing the value of each function everywhere. When the player is allowed to query each function at d+1 points (d being the dimension of the space), we prove regret bounds that are exactly equivalent to full information bounds for smooth functions.