Volumetric spanners: An efficient exploration basis for learning

Elad Hazan, Zohar Karnin

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


Numerous learning problems that contain exploration, such as experiment design, multiarm bandits, online routing, search result aggregation and many more, have been studied extensively in isolation. In this paper we consider a generic and efficiently computable method for action space exploration based on convex geometry. We define a novel geometric notion of an exploration mechanism with low variance called volumetric spanners, and give efficient algorithms to construct such spanners. We describe applications of this mechanism to the problem of optimal experiment design and the general framework for decision making under uncertainty of bandit linear optimization. For the latter we give efficient and near-optimal regret algorithm over general convex sets. Previously such results were known only for specific convex sets, or under special conditions such as the existence of an efficient self-concordant barrier for the underlying set.

Original languageEnglish (US)
Pages (from-to)1-34
Number of pages34
JournalJournal of Machine Learning Research
StatePublished - Apr 1 2016

All Science Journal Classification (ASJC) codes

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


  • Barycentric spanner
  • Hard margin linear regression
  • Linear bandits
  • Volumetric spanner


Dive into the research topics of 'Volumetric spanners: An efficient exploration basis for learning'. Together they form a unique fingerprint.

Cite this