Timezone: »

Bandit Convex Optimization: Towards Tight Bounds
Elad Hazan · Kfir Y. Levy

Tue Dec 09 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D #None

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.

Author Information

Elad Hazan (Technion)
Kfir Y. Levy (Technion)

More from the Same Authors