NIPS Proceedingsβ

Bandit Convex Optimization: Towards Tight Bounds

Part of: Advances in Neural Information Processing Systems 27 (NIPS 2014)

[PDF] [BibTeX] [Reviews]

Authors

Conference Event Type: Poster

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.