Skip to yearly menu bar Skip to main content


Poster

Bandit Convex Optimization: Towards Tight Bounds

Elad Hazan · Kfir Y. Levy

Level 2, room 210D

Abstract:

Bandit Convex Optimization (BCO) is a fundamental framework for decision making under uncertainty, which generalizes many problems from the realm of online and statistical learning. While the special case of linear cost functions is well understood, a gap on the attainable regret for BCO with nonlinear losses remains an important open question. In this paper we take a step towards understanding the best attainable regret bounds for BCO: we give an efficient and near-optimal regret algorithm for BCO with strongly-convex and smooth loss functions. In contrast to previous works on BCO that use time invariant exploration schemes, our method employs an exploration scheme that shrinks with time.

Live content is unavailable. Log in and register to view live content