Volumetric spanners: An efficient exploration basis for learning

Elad E. Hazan, Zohar Karnin, Raghu Meka

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

Numerous machine learning problems require an exploration basis - a mechanism to explore the action space. We define a novel geometric notion of exploration basis with low variance called volumetric spanners, and give efficient algorithms to construct such bases. We show how efficient volumetric spanners give rise to an efficient and near-optimal regret algorithm for bandit linear optimization 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)408-422
Number of pages15
JournalJournal of Machine Learning Research
Volume35
StatePublished - Jan 1 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

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

Cite this