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 .
A related line of work attempts to solve convex optimization problems by instead posing the problem of finding a feasible point from a convex set. Different oracle models of specifying the convex set correspond to different optimization settings. The bandit setting is identical to finding a feasible point, given only a membership oracle for the convex set. Since we get only noisy function evaluations, we in fact only have access to a noisy membership oracle. While there are elegant solutions based on random walks in the easier separation oracle model @cite_8 , the membership oracle setting has been mostly studied in the noiseless setting only and uses much more complex techniques building on the seminal work of Nemirovski and Yudin @cite_10 . The techniques have the additional drawback that they do not guarantee a low regret since the methods often explore aggressively.
@cite_10 @cite_8
2010189695 2106318612
In this paper we consider the multiarmed bandit problem where the arms are chosen from a subset of the real line and the mean rewards are assumed to be a continuous function of the arms. The problem with an infinite number of arms is much more difficult than the usual one with a finite number of arms because the built-in learning task is now infinite dimensional. We devise a kernel estimator-based learning scheme for the mean reward as a function of the arms. Using this learning scheme, we construct a class of certainty equivalence control with forcing schemes and derive asymptotic upper bounds on their learning loss. To the best of our knowledge, these bounds are the strongest rates yet available. Moreover, they are stronger than the @math required for optimality with respect to the average-cost-per-unit-time criterion. Minimizing a convex function over a convex set in n-dimensional space is a basic, general problem with many interesting special cases. Here, we present a simple new algorithm for convex optimization based on sampling by a random walk. It extends naturally to minimizing quasi-convex functions and to other generalizations.