Online Boosting with Bandit Feedback

Nataly Brukhim, Elad Hazan

Research output: Contribution to journalConference articlepeer-review

8 Scopus citations


We consider the problem of online boosting for regression tasks, when only limited information is available to the learner. This setting is motivated by applications in reinforcement learning, in which only partial feedback is provided to the learner. We give an efficient regret minimization method that has two implications. First, we describe an online boosting algorithm with noisy multi-point bandit feedback. Next, we give a new projection-free online convex optimization algorithm with stochastic gradient access, that improves state-of-the-art guarantees in terms of efficiency. Our analysis offers a novel way of incorporating stochastic gradient estimators within Frank-Wolfe-type methods, which circumvents the instability encountered when directly applying projection-free optimization to the stochastic setting.

Original languageEnglish (US)
Pages (from-to)397-420
Number of pages24
JournalProceedings of Machine Learning Research
StatePublished - 2021
Externally publishedYes
Event32nd International Conference on Algorithmic Learning Theory, ALT 2021 - Virtual, Online
Duration: Mar 16 2021Mar 19 2021

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Online Boosting with Bandit Feedback'. Together they form a unique fingerprint.

Cite this